# Question
Title: Showing that deciding whether a given TM accepts a word of length 5 is undecidable
I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this:

Assume that $M\_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts any string of length $5$, i.e., $L(M)$ contains a string of length $5$. The above figure shows how we can use this to construct a Turing Machine that can solve the Halting problem.

The output $M′$ of our translator behaves as follows:

1. $M′$ erases its own input and replaces it with the string w.
2. It them simulates $M$ on $w$.
3. If $M$ halts on $w$, then it goes into a final state (accepts its input). It is clear that if $M$ halts on $w$, $M′$ accepts all its inputs. So it accepts a string of length 5 as well. If $M$ does not halt on $w$, $M′$ does not accept any string at all. So it does not accept any string of length 5 either. So $L(M′)$ includes a string of length $5$ if and only of $M$ accepts $w$. So by running $M\_5$ on $M′$, we can decide if $M$ halts on $w$ or not. But we know that this is not possible since the halting problem is undecidable. Hence $M\_5$ does not exist and the given problem is undecidable.

What I am confused about is: "if $M$ halts on $w$, $M′$ accepts all its inputs" and "If $M$ does not halt on $w$, $M′$ does not accept any string at all". Can someone clarify why this is the case? I've been trying to work out the logic for so long. If any of you guys could help this would be great!

Source

# Answer
To decide if $M$ halts with input $w$, we use the Machine $M'$ that simulates $M$ with input $w$. If $M$ accepts $w$, $M'$ also accepts $w$ (from point 3 of your description). If however $M$ does not halt on input $w$, the simulation can not halt as well.

So far, nothing special has happened.

Now consider point 1 of your description: $M'$ does take an input, but immediately discards it.

So to decide if $M$ halts on $w$, we use $M\_5$ to decide if $M'$ accepts a word of length 5. But $M'$s behavior is completely independent of it's own input, since it just simulates $M$ with fixed $w$.

Now: if $M$ halts on $w$, $M'$ will halt on every input (because it is discarded and $w$ is used instead), especially one of length 5. This will (magically/hypothetically) be detected of $M\_5$.

If however $M$ does not halt on $w$, $M'$ will not halt on any input (again, because the input of $M'$ is irrelevant), especially it will not halt on any input of length 5. This can also be detected by $M\_5$, and we have solved the halting problem.
> 1 votes

# Answer
Suppose that $M$ halts on input $w$ and consider the behaviour of $M'$ when it is given input $w'\\!$. $M'$ first deletes its input $w'$ and replaces it with $w$, which means that the behaviour of $M'$ doesn't depend on what input it actually receives. Then, $M'$ simulates $M$ on input $w$. So, if $M$ halts on $w$, $M'$ halts for every input, becaues $M'$ ignores its input and just pretends to be $M$ running with input $w$. Likewise, if $M$ does not halt on $w$, $M'$ doesn't halt for any input.
> 4 votes

---
Tags: computability, turing-machines, reductions
---


# Question
Title: What is the Big O estimate of a nested for loop?
I am trying to figure out what the big o estimate of the following for loop is.

```
for(int i = 10; i to 100; i++){
for(int j = 1; j to i; j++){
for(int k = 1; k to j; k++){
s=s+i+j;
}
}
}

```

I was thinking that the two inner loops run n times but I am unsure about the first loop.

What would the Big O estimate be for this code?

# Answer
> 3 votes
The whole thing is $O(1)$. This is because the outermost loop has an upper bound of 100 i.e. it is constant, and it bounds the middle loop, which bounds the inner loop. There's a little bit of tricky math to figure out exactly how many times the loop is run, but you can know exactly how many times it is run.

The first hint that this is $O(1)$ is that there are no "free" variables. Pretend the code was linear. What would it be linear in terms of? There are no input parameters. We create $i$,$j$ and $k$, and their values don't change based on some input parameter.

# Answer
> 2 votes
The whole thing has constant running time, since the upper limit of the outer loop is the constant 100 and the inner loops are bounded by the outer loop's value.

---
Tags: algorithms, loops
---


# Question
Title: If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?
> If $A \leq\_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq\_T co\text{-}B$.

Is this true?

My intuition is false even if we can find some special case to make it true such as $A=B=co\text{-}A\_{TM}$. However, I still can't find a counterexample.

Could anyone give me a little hint?

# Answer
> 1 votes
Hint: If $A \leq\_m B$ then there is a computable function $f$ such that $x \in A$ iff $f(x) \in B$ iff it is not the case that $f(x) \in \text{co-}B$. Can you use this to Turing-reduce $A$ to $\text{co-}B$?

---
Tags: computability, reductions
---


title: Breaking up sum of power of 2s

text:
# Question
Title: Breaking up sum of power of 2s
I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays.

I encountered a sub-problem that requires me to break up sums of numbers which are power of 2, i.e. how to find combinations of these numbers that sum up to a certain value. The sum and the combination size are given. Also only 4 power of 2s can be present in a combination: `2,4,8,16`.

Lets suppose I have a sum of `8` and I need to break up into a set of `3` numbers. The result would invariably be `[2,2,4]`.

If I need to break up `20` into 3 power of 2s, I could have `[2,2,16]` or `[4,8,8]`.

Naturally larger sets will result in many possible combinations.

My aim is to write an algorithm that obtains all possible combinations as efficiently as possible. I'm not looking for the algorithm itself, but some leads into how to partition the number. What are some properties of power of 2s that I need to use to partition a sum into a possible combination?

# Answer
Look at the binary representation of the sum. Each `1` in that representation represents a power of two that has to be included as a summand, either directly or indirectly.

If the number of `1`s in that representation is greater than the number of summands, there is no solution, if it is equal, there is exactly one solution, and if it is smaller, things get interesting.

The basic property you'll want to exploit in the last case is that you can represent any power of two as once that power, or twice the next smaller power, or 4 times the one after that and so on.

I think this approach can lead to an efficient algorithm. (But I did not follow it through myself, so no guarantees.)
> 3 votes

# Answer
First, note that there could be exponentially (in input length) many such partitions. For example, consider $$ 4 + 4^2 + \cdots + 4^{2n}. $$ There are at least $\binom{2n}{n} = \Theta(4^n/\sqrt{n})$ such partitions with $3n$ parts.

Here is a naive algorithm which should be quite efficient. Suppose we want to split $n$ into $k$ parts. Write $n = 2a + b$, where $b \in \\{0,1\\}$, and let $\ell$ be the number of 1's in the binary representation of $a$. For $\max(0,k-b-a)/2 \leq t \leq (k-\ell-b)/2$, compute all representations of $a-t$ with $k-b-2t-a$ parts (recursively), multiply them by 2 and add $2t+b$ copies of 1. We have chosen the bounds on $t$ so that for every choice of $t$ there is at least one representation of $a-t$ with $k-b-2t-a$ parts.
> 1 votes

---
Tags: algorithms, number-theory
---


title: Difference in CPU Wattage Question

text:
# Question
Title: Difference in CPU Wattage Question
If I have 2 CPU's of the same manufacturer... say AMD

Both are Quad-Core, Both are rated at 3.6Ghz

1 is 100W, the other is 65W

Will the one with the higher wattage out-perform the lower one and why?

# Answer
Here is an analogy from the world of light bulbs. An incandescent light bulb operates at 15LPW (Lumens per Watt), while a LED light bulb operates at 45LPW. Suppose for the moment that both give the same spectrum of light (which is wrong). Suppose we feed the incandescent light bulb 9 Watts and the LED light bulb 3 Watts. Both will produce 105 Lumens, but the LED light will be more efficient.

The example with the CPUs is the same. Different technologies result in different power efficiency, but otherwise they could have the same *effectiveness*, e.g. as measured by FLOPS. The only way to answer your question is to check the specs of the CPUs — CPU frequency is only part of the picture.
> 2 votes

---
Tags: cpu-cache, cpu-pipelines
---


# Question
Title: Intersection/Union of recursively enumerable languages that aren't decidable?
For $L\_1,L\_2 \in RE - R $ , I want to prove or disprove if the following can occur:

1. $L\_1 \cap L\_2 \in R$
2. $L\_1 \cup L\_2 \in R$
3. $L\_1 \cap L\_2 \in R$ and $L\_1 \cup L\_2 \in R$

**What I did:**

1. I think any two disjoint languages suffice, since the empty set is decidable.
2. I think something along the lines of a language and its complement but I'm struggling to think of an example.
3. It seems impossible but I have no idea how to prove it.

Any help/further insight would be welcomed!

# Answer
1. **Correct.** We can have $L\_1\cap L\_2=\emptyset\in R$. A good answer would give an example of such a pair $L\_1$, $L\_2$ so you should figure that out on your own.
2. **Correct** but for the wrong reason. If $L\_1$ and its complement are both $RE$, then both are recursive and the question says that neither is recursive. You should prove this yourself, as you'll need it for the next part.

* **Hint** for this proof: show how to use machines that accept $L\_1$ and $\overline{L\_1}$ to give a machine that decides $L\_1$.)
    * **Hint** for the question: take a recursives language $K\_1$ and $K\_2$ and set $L\_1=K\_1 \cup \text{something}$ and $L\_2=K\_2\cup\text{something else}$ in a way that gives $L\_1\cup L\_2=K\_1\cup K\_2$.
3. **Correct.** We know that $L\_1\in RE$. Use $L\_1\cap L\_2\in R$ and $L\_1\cup L\_2\in R$ to show that $\overline{L\_1}\in RE$. By the extra proof I suggested you do in the previous part, that means that $L\_1\in R$, contradicting the requirement that $L\_1\in RE\setminus R$.
> 4 votes

# Answer
Hint for 2: Consider $L\_1 = \\{ 0 w : w \in L \\} + \\{ 1 w : w \in \\{0,1\\}^\* \\}$ and let $L\_2$ be a complementary language.

Hint for 3: $L\_2 \setminus (L\_1 \cap L\_2) = \overline{L\_1} \cap L\_2$ and $\overline{L\_1 \cup L\_2} = \overline{L\_1} \cap \overline{L\_2}$.
> 2 votes

---
Tags: formal-languages, turing-machines
---


title: Big O running time for this algorithm?

text:
# Question
Title: Big O running time for this algorithm?
Here's the code for the algorithm:

```
Foo(n)
   lcm = 1
   for i = 2 to n
       lcm = lcm*i/Euclid(lcm,i)
return lcm

```

The running time of `Euclid`$(a, b)$ is given as $O(\log(\min(a, b)))$

So the running time of the for loop will be $O(n)$, so would this be the final running time? or do I have to take the $O(\log(\min(a, b)))$ into account as well?

# Answer
> 3 votes
The running time for the loop will be $$ O\left(\sum\_{i=2}^n (1+\log \min(\operatorname{lcm}(1,2,\ldots,i-1),i))\right). $$ The $1$ takes care of the arithmetic operations beyond GCD, and the other term is the running time of GCD, as given to your. The arguments to GCD are `lcm` and `i`. The value of `lcm` at iteration $i$ is $\mathrm{lcm}(1,2,\ldots,i-1)$, explaining the complete formula.

We can upper bound this sum by $$ O\left(\sum\_{i=2}^n (1 + \log i)\right) \leq O\left(\sum\_{i=2}^n (1 + \log n)\right) = O(n\log n). $$

---
Tags: algorithms, runtime-analysis
---


title: Time Complexity of Halley's Method

text:
# Question
Title: Time Complexity of Halley's Method
What is the time complexity of Halley's Method?

I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity in order to yield the greater convergence. However, I can't seem to find any solid ground to support any of my ideas (as nobody has ever seemed to have asked this question on the internet before)...

Halley's Method - Wikipedia

# Answer
I'm assuming $n$ is the accuracy needed (in bits). Assuming that your starting point is reasonable, you converge in $O(\log n)$ iterations, just as in Newton's method. The *absolute* number of iterations is smaller than in Newton's method — Newton's method converges in $\log\_2 n$ rounds, Halley's in $\log\_3 n$ rounds (roughly speaking). However, this difference is lost in big O notation. For this reason, when analyzing methods like this, it is more meaningful to count function evaluations, keeping in mind that derivatives (and second derivatives in the case of Halley's method) may have a different complexity than the function itself.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis
---


# Question
Title: Is there a model of computation, that tries to be realistic?
For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things about everyday algorithms on an everyday computer.

I want a model that makes computations in a ring, namely $\Bbb{Z}\_p\times \dots \times \Bbb{Z}\_p = (\Bbb{Z}\_p)^k$, where $p$ is prime (for a good reason... later on that). Since that's what bytes on a computer look like they look like values in $\Bbb{Z}\_8$ and even some of the instructions on those bytes on modern computers cause wrap around that looks like that of $\Bbb{Z}\_8$. It's obvious to me that any computation on my home PC can be done with computations in said ring. But of course I'd have to prove that formally if I wrote a paper. I can already write conditional assignments of a memory slot (element of $\Bbb{Z}\_p$), as the value of a polynomial in $\Bbb{Z}\_p\[x\_1, \dots, x\_k\]$.

It's hard to find literature on this, but to me it seems so obvious that this is a nice approach and I'm shocked that no one's considered this yet. Or have they? Links please...

# Answer
As D.W. mentions in the comments, the model you are looking for is the RAM machine. In fact, there are several different models, and I recommend the following recent paper of Fürer's for a good overview.

In contrast to what you describe, the correct ring is $\mathbb{Z}\_{2^n}$, where $n$ is the width of registers – up to 512 bits in future Intel processors. The exact value of $n$ doesn't matter at all as long as it's constant, since in computational complexity we are always interested in time and space complexity up to a multiplicative constant. Therefore, to make matters interesting, the RAM models described above let $n$ depend on the input size.

Regarding finitude of memory, this is captured, to some extent, by space constraints – polynomial space (or linear/quasilinear space) for algorithms working on normal data, logarithmic space (or polylogarithmic space) for algorithms working on big data; there are also streaming models for even less space. Restricting the space altogether would be destructive since then all deterministic algorithms would terminate in constant time – to make sense of asymptotics, we must allow space to grow with input size.
> 6 votes

---
Tags: reference-request, machine-models
---


# Question
Title: Can every program be turned into a quine?
Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't find anything with some googling, but it seems like the kind of thing that could be known.

# Answer
You are looking for the recursion theorem. Let $F(e)$ be the function that on input $0x$ returns $P(x)$ and on input $1x$ returns $e$. A fixed point $\varphi\_e = \varphi\_{F(e)}$ is what you're looking for.

If you're interested in how this quine is constructed, take a look at the proof, for example here.
> 5 votes

---
Tags: computability
---


# Question
Title: The min cut capacity in a network based on a bipartite graph (Hall's Theorem)
Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5,

> The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is $\text{Capacity}(S) = |L\_2|+|R\_1|+\text{edges}(L\_1, R\_2)$.

Here, $L\_1 = S \cap L$, $L\_2 = L \setminus S$, $R\_1 = S \cap R$ and $R\_2 = R \setminus S$. Furthermore, $L$ are the left edges and $R$ are the right edges.

I don't understand how he arrived at the conclusion that

> number of edges that go from $S$ to $\overline{S} = |L\_2|+|R\_1|+\text{edges}(L\_1, R\_2)$

I don't understand the meaning of this expression. I drew it out on paper (highlighting all graph elements of the expression) and I still don't get it. Could somebody please explain to me how this expression is generated in simple and detailed terms?

# Answer
The flow network $G'$ is constructed from the original bipartite graph $G=(L,R,E)$ by adding two new nodes $s,t$, connecting $s$ to all nodes in $L$, connecting all nodes in $R$ to $t$, and orienting all edges in $E$ from $L$ to $R$. And $s$-$t$ cut in $G'$ has the form $(S,\overline{S})$ where $s \in S$, $t \in \overline{S}$. The edges crossing the cut are:

1. Edges from $s$ to $\overline{S}$, that is, from $s$ to $\overline{S} \cap L$. There are $|L\_2|$ of these.
2. Edges from $S$ to $t$, that is, from $S \cap R$ to $t$. There are $|R\_1|$ of these.
3. Edges from $S \setminus \\{s\\}$ to $\overline{S} \setminus \\{t\\}$, that is, from $S \cap L$ to $\overline{S} \cap R$. There are $\mathrm{edges}(L\_1,R\_2)$ of these.

It is crucial that in $G'$ the edges are oriented, and that when counting edges crossing the cut $(S,\overline{S})$, we only count edges going from $S$ to $\overline{S}$.
> 3 votes

---
Tags: graphs, bipartite-matching
---


# Question
Title: Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths
Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (extracted from the final residual network) can also be used to determine the minimum vertex cover:

$$(X\cap T)\cup(Y\cap S)$$

If this expression is a correct alternative, I don't have an intuition for why it's true. The best intuition I've been able to come up with is: Select each vertex on the left (X) that has a positive flow leading up to it and select each vertex on the right if there is no flow leading up to it. Why is this set equal to the minimum vertex cover?

# Answer
> 2 votes
The set $(X \cap T) \cup (Y \cap S)$ is the same as the one given by the alternating path algorithm. Let $L\_0,L\_1,\ldots$ be the subsets considered in the alternating path algorithm (in the Wikipedia page they are called $S\_0,S\_1,\ldots$, but that will be confusing), and let $X\_i = L\_i \cap X$, $Y\_i = L\_i \cap Y$.

* A vertex $x \in X\_0$ is unmatched and so the edge from $s$ to $x$ is in the residual network, showing that $x \in S$. In other words, $X\_0 \subseteq S$. Analogously, $Y\_0 \subseteq T$.
* A vertex $x \in X\_1$ is connected to some $y \in Y\_0$ via some edge not in the matching. Since $(x,y)$ is not in the matching, it belongs to the residual network. Since $y \in T$, also $x \in T$. In other words, $X\_1 \subseteq T$. Analogously, $Y\_1 \subseteq S$.
* A vertex $x \in X\_2$ is connected to some $y \in Y\_1$ via some edge not in the matching. As before, $(x,y)$ belongs to the residual network, and so $y \in S$ implies $x \in S$. In other words, $X\_2 \subseteq S$ and $Y\_2 \subseteq T$.

Continuing this way, we conclude that $$ \begin{align\*} S \cap X &= X\_0 \cup X\_2 \cup \cdots, & T \cap X &= X\_1 \cup X\_3 \cup \cdots, \\ S \cap Y &= Y\_1 \cup Y\_3 \cup \cdots, & T \cap Y &= Y\_0 \cup Y\_2 \cup \cdots. \\ \end{align\*} $$ Therefore $$ (X \cap T) \cup (Y \cap S) = X\_1 \cup X\_3 \cup \cdots \cup Y\_1 \cup Y\_3 \cup \cdots = L\_1 \cup L\_3 \cup \cdots, $$ which is the output of the alternating path algorithm.

---
Tags: graphs, network-flow, bipartite-matching
---


# Question
Title: How to find out what are accept, loop and reject in this Turing Machine?
I am trying to find out accept, loop and reject in this Turing Machine because it doesnt have any...I am not sure if I completely understand it but this is the turing machine I am talking about...

so accept state would be --\> `Accept(T2) - all words with a a`
loop state would be --\> `Loop (T2) - /\`

reject state would be --\> `Reject(T2) - Strings with b`

am I on a right track ? how could I do find accept, loop and reject on this TM? thanks!

# Answer
> 2 votes
Yuval's answer applies to your machine T$\_2$. With his assumptions, we have the following behavior for your T$\_1$ on possible inputs:

* It will reject the empty string, since there is no move defined on the "blank" symbol.
* It will not accept any string consisting only of $a$ characters, since it won't reach the HALT state.
* It will accept $a\dots ab$, since it will reach the HALT state.
* If the input is a single $b$, it will enter the HALT state and will then fall off the left end of the tape. Whether that should lead to acceptance or rejection depends on your definition of "accept" and "reject".
* Whether it will accept a string like $aba$ or $abb$ will depend on your definition of "accept", since in these cases it will enter the HALT state and will never process the characters beyond the first $b$.
* There is no loop state, at least under Yuval's and my interpretation.

You need to look closely at your local definition of a TM, since there are several forms they might take and of course we have no way of knowing what definitions you're using.

# Answer
> 1 votes
Your terminology is non-standard, but I assume that:

* The Turing machine *accepts* when it reaches the HALT state.
* The Turing machine *loops* if it never terminates.
* The Turing machine *rejects* if it gets "stuck", i.e., at some state it sees some symbol $\alpha$ but there is no outgoing arrow labelled $\alpha$.

Assuming this terminology, your answer is almost correct:

* Inputs starting with $aa$ are accepted.
* No inputs result in an endless loop.
* All other inputs are rejected.

You claimed that all inputs having $b$ are rejected (you're assuming the alphabet is $\\{a,b\\}$). This is correct, but there are a few other strings which are also rejected – can you see which?

---
Tags: terminology, turing-machines
---


# Question
Title: Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?
Is the language $L = \\{a^nb^m : n = 2^m\\}$ context-free?

Assume L is a context-free language. Then $\ \exists p\in \mathbb{Z}^{+}:\forall s\in L\left | s \right |\geq p. s = uvxyz,\left | vy \right |\geq 1,\left | vxy \right |\leq p. s\_i = uv^{i}xy^{i}z\in L\forall i\geq 0\ $.

Let s = $\ a^{2^p}b^{p}\ $

Pumping i times will give a string of length $\ 2^{p} + (i - 1)\*j\ $ a's and $\ p + (i - 1)\*k\ $ b's where $\ 1 \leq j + k \leq p\ $

Case 1: $\ j \neq 0\ $ $\ k \neq 0\ $

??

Case 2: $\ j = 0\ $ $\ k \neq 0\ $

??

Case 3: $\ j \neq 0\ $ $\ k = 0\ $

??

It can be concluded from this that L is not a context-free language.

# Answer
You have stated that pumping $s$ $i$ times will give a string which contains $2^p+(i-1)\*j$ $a$'s and $p+(i-1)\*k$ $b$'s where $1 \le j+k \le p$. For the given language $L$ to be a CFG, new string must also belong to $L$ for all valid values of $i$.

Put $i=2$. This gives a string containing $2^p+j$ $a$'s and $p+k$ $b$'s. For this to be of the form $a^{2^m}b^m$, we need $$2^{p+k} = 2^p+j$$ This implies $$j = 2^p\*(2^k-1)$$

Case 1: If $k = 0$, then from the above equation, $j$ must be $0$. But, this implies, $|vy| = 0$. So, this case is not possible

Case 2: If $k \ne 0 $, then $j \ge 2^p \ge p$, but this is also not possible since $|vy| \le p$. So, the equation $$j = 2^p\*(2^k-1)$$ is not possible.

Therefore, we cannot split the string $s = a^{2^p}b^p$ satisfying all constraints. So, the language $L$ is not Context Free.
> 3 votes

---
Tags: pumping-lemma
---


# Question
Title: Recognizing interval graphs--"equivalent intervals"
I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper:

> Each interval graph has a corresponding interval model in which two intervals overlap if and only if their corresponding vertices are adjacent. Such a representation is usually far from unique. To eliminate uninteresting variations of the endpoint orderings, we shall consider the following block structure of endpoints: Denote the right (resp. left) endpoint of an interval $u$ by $R(u)$ (resp. $L(u)$). In an interval model, define a maximal contiguous set of right (resp. left) endpoints as an R-block (resp. L-block). Thus, the endpoints can be grouped as a left-right block sequence. Since an endpoint block is a set, the endpoint orderings within a block are ignored. It is easy to see that the overlapping relationship does not change if one permute the endpoint order within each block. Define two interval models for $G$ to be equivalent if either their left-right block sequences are identical or one is the reversal of the other.

I am unable to understand the notion of equivalent intervals. Can someone help me?

# Answer
> 3 votes
Imagine scanning the real line from left to right. Whenever an interval starts or ends, you make notice of it. For example, perhaps at some representation, at the point $3$ the intervals for $x\_2,x\_7$ start and the interval for $x\_{15}$ ends, and at the point $4$ the interval for $x\_2$ ends, and no points occur in between.

Suppose we "remove" the portion $(3.25,3.75)$ of the real line, thus pushing the point $4$ back to $3.5$. This only affects the value of some ordinates, so we would like to say that these two interval representations are "the same". Indeed, they are equivalent under the definition you give, since if we make a list of which intervals start and end at what point, then the lists would be identical, the only difference being the value of the ordinates.

Another operation we can do is reflecting the real line, say around zero. Now the interval for $x\_2$ is $(-4,-3)$ instead of $(3,4)$, so that at the point $-4$ the interval $x\_2$ starts, and at the point $-3$ the intervals for $x\_2,x\_7$ end and the interval for $x\_{15}$ starts. Again, we would like both of these representation to count as "the same". This transformation is captured by the reversal clause in the definition you quote.

---
Tags: algorithms, graphs, intervals
---


# Question
Title: Is there a general-case sweep line algorithm for line segment intersection?
I'm looking for a sweep line algorithm for finding all intersections in a set of line segments which doesn't necessarily require the general position constraint of Bentley-Ottman's algorithm (taken from Wikipedia):

* No two line segment endpoints or crossings have the same x-coordinate
* No line segment endpoint lies upon another line segment
* No three line segments intersect at a single point.

Is there any sweep line solution to this problem? If not, is there any other algorithm that solves this problem in $\mathcal{O}((n+k) \log(n))$?

# Answer
> 2 votes
Usually these algorithms can be adapted to the general case, but the details are messy and hard to get right. Another option is *perturbation*:

* Move each line segment by some small amount in all directions.
* Extend the segments slightly on both ends.

If you choose your parameters carefully (i.e., small enough), you are likely to have all the same intersections, but you will be in general position with probability 1. How small is small depends on your input, and this is a limitation of this approach, but in practice you can probably heuristically choose a small enough perturbation.

Implementing this using "virtual infinitesimals", you can come up with a version of Bentley–Ottman that doesn't require general position. The idea is to do the perturbation by some infinitesimal amount, and record the results *formally* (e.g. $1$ goes to $1+\epsilon$, where $\epsilon$ is an infinitesimal). When running the algorithm, you will need to compare values which involve these infinitesimals, which you can do formally (for example, $1+\epsilon \< 1 + 2\epsilon$).

---
Tags: algorithms, computational-geometry
---


# Question
Title: Can a Post machine have more than one accepting state?
I was searching through Google and I couldn't find anything.

Can a Post machine have more than one accepting state?

# Answer
According to the description on Wikipedia, there could be more than one accepting state. The truth is, it doesn't matter. The model with a single accepting state and the model with many accepting states are equivalent. A machine of the former kind is also a machine of the latter kind. In the other direction, starting with a machine with many accepting states, single out one of them as the "real" accepting state, and add transitions from the other states to the chosen accepting state.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?
On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s. Each element of the matrix must be either zero or one.

I came up with a recursive solution for an $N \times 10$ matrix. Subproblems are indexed by the counts $c\_k$ of how many columns have $k$ $1$'s, for $k =0, 1,2,3,4,5$. The counts $c\_k$ have to satisfy $\sum\_k c\_k = 10$, and they also have to satisfy $\sum\_k kc\_k = 5N$ and $c\_k = 0$ for $k \> N$. The complexity of this algorithm basically boils down to how many distinct sets of valid indices $(c\_k)\_k$ there are.

For a $10 \times 10$ matrix I think this approach should work out nicely, but I worry the complexity might get prohibitively large if we wanted to count how many ways to get $M/2$ $1$'s in every row and column of an $M \times M$ matrix. So I'm wondering, is there a more efficient way to solve this counting problem? In other words, a better way than solving for $N \times M$ in increasing order of $N$ and keeping track of subcases indexed by $(c\_k)\_k$ such that $\sum\_k c\_k = M$ and $\sum\_k k c\_k = NM/2$? Also, for my solution, can anybody work out a good bound for how many sub-cases I have as a function of $M$?

# Answer
> 4 votes
When $k = 1$ then answer is $M!$ (why?). In the general case, an explicit formula is probably too much to hope for, but it is possible to obtain asymptotics. For example, in this answer Brendan McKay shows that for $k=2$, the number of ways is asymptotically $e^{-5/2} (2n)! 4^{-n}$ *when the diagonal is always zero*. Without the condition on the diagonal, the answer will be $e^{-1/2} (2n)! 4^{-n}$ (I think). The same method, known as the *configuration model*, should give asymptotics for arbitrary $k$.

# Answer
> 2 votes
Short summary: Your algorithm should be very efficient; it looks like it only has to explore tens of thousands of subcases, at most. See the second half of this answer for a detailed analysis. However, there are other more general approaches that can also be used for this problem, which I will list next. They may be of independent interest, because they can be used for other sorts of counting problems in this vein.

## Alternative approaches

Have you tried using MINION, a solver intended for counting the number of solutions to a constraint satisfaction problem? It looks like your problem should be encodable in MINION's input language.

You could also try any #SAT solver. A #SAT solver counts the number of satisfying assignments to a particular formula $\varphi$, provided in SAT. It would be easy to write down a SAT formula on 100 unknowns that is satisfied exactly by the $10\times 10$ matrices with five zeros and five ones in each row and column. Then, you could try any off-the-shelf #SAT solver and see how efficient it is.

I don't know how well these will deal with the high amount of symmetry present in this problem, but it wouldn't be too hard to give them a try and see.

For more on these subjects, see the following two questions:

Another option, as suggested by Steven Stadnicki, is to express the set of valid matrices as a BDD. You should be able to construct a BDD on 100 variables that represents the set of all valid matrices, i.e., the set of satisfying assignments to the formula $\varphi$. Then, there are standard constructions to count the number of solutions to a BDD, using dynamic programming (see e.g., Knuth, vol. 4, TAOCP). This is a great suggestion. You'll have to try it to see how large a BDD you get; asymptotically, the size of the BDD will be exponential in the dimensions of the matrix, but for a $10 \times 10$ matrix, if you pick a good variable ordering, it's plausible that the BDD might be small enough that you can make this approach work for your particular problem. Credit to Steven Stadnicki for this suggestion.

## Efficiency of your approach

You also asked about the efficiency of your approach, and in particular, the number of subcases it will explore. We can analyze this by looking at the number of partitions of an integer. The number of partitions of $n$ is denoted $p(n)$. For instance, $p(3)=3$, since the three partitions are $3=3$, $3=2+1$, $3=1+1+1$.

For starters, let's look at the number of subcases you examine for $M=6$ (i.e., when examining $6 \times 10$ matrices). With a bit of thinking, you can realize that each subcase corresponds to a unique partition of $30$. For instance, the subcase where you want column sums of $4,4,4,3,3,3,3,2,2,2$ (in your notation, $c\_0=c\_1=c\_5=0$, $c\_2=3$, $c\_3=4$, $c\_4=3$) corresponds to the partition $30=4+4+4+3+3+3+3+2+2+2$. Thus, the set of subcases is a subset of the set of partitions of $30$. (Not every partition of $30$ corresponds to a subcase; only those partitions where each summand in the partition is in the range 1..5.) Therefore, the number of subcases is $\le p(30)$. Consulting OEIS, we find that $p(30)=5604$.

It follows that for the case $M=6$, where you examine $6 \times 10$ matrices, your algorithm explores at most 5604 subcases.

This analysis can be generated to all $M \ge 6$. For $M=7$, it naively looks like we're looking at partitions of $35$: except that each summand must be in the range 2..5, and there must be exactly 10 summands. If we subtract one from each summand, we get a partition of $25$ (where each resulting summand is in the range 1..4). Therefore, the number of subcases for $M=7$ is $\le p(25)=1958$. By the same reasoning, the number of subcases for $M=8,9,10$ is at most $p(20),p(15),p(10)$, i.e., at most $627, 176, 42$, respectively.

Next, let's look at $M=5$. Now the column sums are in the range 0..5, and they must sum to $25$. One loose bound can be obtained by adding one to each column sum, and noting that each subcase corresponds to a partition of $35$ where all summands are in the range 1..6; there are thus $\le p(35)=14883$ such subcases. A slightly better bound can be obtained by counting the number $c\_0$ of columns whose column sums are $0$; for each fixed $c\_0$, the number of subcases is $\le p(25)$ (since the other column sums sum to $25$). The number $c\_0$ can be anything in the range 0..5. Therefore, the total number of subcases is $\le 6 \times p(25) = 11748$.

What about $M=4$? Here the column sums are each in the range 0..5, and they must sum to $20$. Repeating the above reasoning gives one upper bound $\le p(30) = 5604$. The slightly better upper bound is $\le 7 \times p(20) = 4389$.

Continuing in this way, for $M=3,2,1,0$ the number of subcases is at most $1408,378,70,1$. I'm sure you can get better bounds for many of these cases, but this is sufficient to give an upper bound on the number of subcases.

Summing this up over all $M$, we find that the total number of subcases is at most

$$1+70+387+1408+4389+11748+5604+1958+627+176+42 = 26410.$$

Therefore, your algorithm explores at most 26410 subcases. (This is a conservative upper bound and the true number will be lower than this.) This is small enough that your algorithm should be very efficient, for the case of $10 \times 10$ algorithms.

---
Tags: algorithms, time-complexity, combinatorics
---


# Question
Title: Information loss of a 9-input majority gate
According to information theory, the logic gates AND, NAND, OR, NOR all lose 1.189 bits of information each with two bits of information at their inputs and with all inputs being independently and uniformly distributed.

When gates are used in combination with other gates in a circuit, to calculate the entropy loss for the entire circuit you have to use what are called "mixture probabilities" or "mixing distributions" to calculate the entropy loss, the loss for each gate being dependent on the entropy loss history of the preceding gates.

Can anyone calculate the entropy loss of a majority gate with 9 inputs, all equally likely $\\{1,0\\}$?

# Answer
Let me first explain what the *entropy loss* is for a gate like AND. The input entropy is $2h(1/2) = 2$ (where $h(p) = -p\log\_2p-(1-p)\log\_2(1-p)$), while the output entropy is $h(1/4)$ (since the probability that the output is $1$ is $1/4$). Therefore the entropy loss is $2 - h(1/4) \approx 1.189$.

In the case of recursive majority, the output is uniform, so the output entropy is $1$. The input entropy, in contrast, is $9$, and so the entropy loss is $9-1=8$.
> 0 votes

---
Tags: information-theory
---


# Question
Title: Control flow graphs - Tree decomposition
Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example :

```
While A
if B
do ..
else do ..
end while

```

For above example, while doing decomposition, I can say its

> D2 (D1)

i.e while and then inside while, its if-then-else.

Considering same situation. How can you represent

> CONTINUE and BREAK statements

Ever for `FOR statement` there is no defined terminology like for `while` and `if then else`. `FOR statement` falls under `while`.

My prof says in theory, there is nothing about `Break and continue statement` and I couldnt find anything online too.

For example :

```
# include <stdio.h>
int main(){
   float num,average,sum;
   int i,n;
   printf("Maximum no. of inputs\n");
   scanf("%d",&n);
   for(i=1;i<=n;++i){
       printf("Enter n%d: ",i);
       scanf("%f",&num);
       if(num<0.0)
       break;                     //for loop breaks if num<0.0
       sum=sum+num;
}
  average=sum/(i-1);
  printf("Average=%.2f",average);
  return 0;
}

```

Control flow graph for this is as below: the nodes has line number written : (Sorry the image is side ways)

I decomposed this as :

```
P1;P1;D2(P1;P1;D1);P1

* P1 represents set of statements outside loops

```

I'm not sure if this is correct. My professors says to use something as D22 for break, like create a new term from above image.

> My main question here is the decomposition. I Know that i drew the CFG correctly, but is the decomposition correct according to the first image?. The break state kind of creates a while as you can see in CFG, but i'm not sure if it has to be considered as while and I guess we cannot, as per my professor.

I am working on this and wanted to know, if anyone has come across something for Break and continue statements while decomposition of graphs, please let me know.

Thanks.

PS : Please, Let me know, if am unclear and if anymore info is needed. I can probably write down an example and upload the picture.

# Answer
There are many different kinds of control-flow constructs that only map to "structured programming" (tree decomposition) constructs when you add extra data variables and extra tests. `continue` is usually okay (as long as its not nested any deeper), but `break` is one of the hard ones. Another relatively painful case is short-circuit conditional evaluation.

A preprocessing step of converting `while x stmt` to `if x repeat stmt until not(x)` will make everything a little easier (and you want to do this anyway, because it lets you safely optimize loop invariants). Example:

```
while i<=n:
  something
  if condition break
  something_else
  i = i+1

```

becomes

```
if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
  until not(i<=n)

```

A second preprocessing step of saving the (possibly complicated) calculation of the loop condition as a boolean temporary variable will also help. So:

```
if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
    t0 = not(i<=n)
  until t0

```

Now we can convert our `break` into a `if-else`:

```
if i<=n:
  repeat:
    something
    if condition:
      t0 = false
    else:
      something_else
      i = i+1
      t0 = not(i<=n)
  until t0

```

So we've converted, but the result is kind of ugly: we now have to keep track of `t0` *and* we have two tests where we only had one before. "Structured programming" is not the panacea it is often made out to be.
> 5 votes

---
Tags: graphs, software-engineering, software-testing
---


# Question
Title: Convex Hull algorithm - why it can't be computed using only comparisons
Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that:

> The standard $\Omega(n \log n)$ lower bound for sorting is proven in the decision tree model of computing, in which only numerical comparisons but not arithmetic operations can be performed; however, in this model, convex hulls cannot be computed at all.

Why is it so? I can't find any justification for it anywhere, I know it to be intuitively true, but how come it's a necessity?

# Answer
Consider the set of points $(0,0),(1,1.2),(0,2),(0.5,0.65)$ versus the set of points $(0,0),(1,1.2),(0,2),(0.5,0.55)$. The last point belongs to the convex hull only in the second set. However, if you compare any two ordinates in the two situations, you will get the same answer.
> 5 votes

# Answer
For a slightly more general way of looking at this, what you want to do is equivalent to saying you can reconstruct the convex hull from the orderings induced by projections onto the coordinate axes.

To see you can't do this, just observe that for three points $a$, $b$, and $c$, knowing that $a \< c \< b$ in both projections doesn't let you figure out whether $c$ is above, below, or on the segment $ab$. (Start with $c$ on the segment and then perturb it up or down by a small amount.)

This indicates that you'll need the "left turn" and "right turn" predicates.
> 6 votes

---
Tags: algorithms, computational-geometry, computation-models
---


# Question
Title: What can Idris not do by giving up Turing completeness?
I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types?

I guess this is quite a specific question, but I don't know a huge amount about dependent types and related type systems.

# Answer
> 58 votes
Idris is Turing Complete! It does check for totality (termination when programming with data, productivity when programming with codata) but doesn't require that everything is total.

Interestingly, having data and codata is enough to *model* Turing Completeness since you can write a monad for partial functions. I did this, years ago, in Coq - it's probably bitrotted by now but here it is nevertheless: http://eb.host.cs.st-andrews.ac.uk/Partial/partial.v.

You do need one escape to actually run such things, but Idris allows you to do that.

Idris won't reduce partial functions at the type level, in order to keep type checking decidable. Also, only total programs can reasonably be believed as proofs.

# Answer
> 17 votes
First, I assume you've already heard of the Church-Turing thesis, which states that anything we call “computation” is something that can be done with a Turing machine (or any of the many other equivalent models). So a Turing-complete language is one in which any computation can be expressed. Conversely, a Turing-incomplete language is one in which there is some computation that cannot be expressed.

Ok, that wasn't very informative. Let me give an example. There is one thing you cannot do in any Turing-incomplete language: you can't write a Turing machine simulator (otherwise you could encode any computation on the simulated Turing machine).

Ok, that *still* wasn't very informative. the real question is, what *useful* program cannot be written in a Turing-incomplete language? Well, nobody has come up with a definition of “useful program” that includes all the programs someone somewhere has written for a useful purpose, and that doesn't include all Turing machine computations. So designing a Turing-incomplete language in which you can write all useful programs is still a very long-term research goal.

Now there are several very different kinds of Turing-incomplete languages out there, and they differ in what they can't do. However there is a common theme: Turing-complete languages must include some way to conditionally terminate or keep going for a time that is not bounded by the program size, and a way for the program to use an amount of memory that depends on the input. Concretely, most imperative programming languages provide these abilities through while loops and dynamic memory allocation respectively. Most functional programming languages provide these abilities through recursion and data structure nesting.

Idris is strongly inspired by Agda. Agda is a language designed for proving theorems. Now proving theorems and running programs are very closely related, so you can write programs in Agda just like you prove a theorem. Intuitively, a proof of the theorem “A implies B” is a function that takes a proof of theorem A as an argument and returns a proof of theorem B.

Since the goal of the system is to prove theorems, you can't let the programmer write arbitrary functions. Imagine the language allowed you to write a silly recursive function that just called itself:

```
oops : A -> B
oops x = oops x

```

You can't let the existence of such a function convince you that A implies B, or else you would be able to prove anything and not just true theorems! So Agda (and similar theorem provers) forbid arbitrary recursion. When you write a recursive function, you must *prove that it always terminates*, so that whenever you run it on a proof of theorem A you know that it will construct a proof of theorem B.

The immediate practical limitation of Agda is that you cannot write arbitrary recursive functions. Since the system must be able to reject all non-terminating functions, the undecidability of the halting problem (or more generally Rice's theorem) ensures that there are terminating functions that are rejected as well. An added practical difficulty is that you have to help the system to prove that your function does terminate.

There is a lot of ongoing research on making proof systems more programming-language-like without compromising their guarantee that if you have a function from A to B, it's as good as a mathematical proof that A implies B. Extending the system to accept more terminating functions is one of the research topics. Other extension directions include coping with such “real-world” concerns as input/output and concurrency. Another challenge is to make these systems accessible to mere mortals (or perhaps convince mere mortals that they are in fact accessible).

I'm not familiar with Idris. It is a take on the challenges I just mentioned. As far as I understand from a cursory glance at the 2013 preprint, Idris *is* Turing-complete, but includes a totality checker. The totality checker verifies that every function annotated with the keyword `total` terminate. The language fragment that only contains Idris programs where every function is total is similar in expressive power to Arda (probably not an exact match due to differences in the type theory, but close enough that you wouldn't notice unless you deliberately tried).

For other examples of languages that are not Turing-complete in different ways, see What are the practical limitations of a non-turing complete language like Coq? (which this answer is to a large extend taken from).

---
Tags: computability, programming-languages, type-theory, dependent-types
---


# Question
Title: Efficient lookup when key is made of multiple elements and elements can be empty
I am wanting to create a map where the key contains multiple elements and the elements can be empty/null. The empty values are treated as "anything". I want to lookup function to match when the stored key is the lookup value or it is a generalised version - index key has empties where lookup value has values. I think the formalisation would be "the lookup value logically subsumes the index-key". I also want the lookup function to return the most specific index-key, that is the key with the fewest empties.

For example, if the data is stored in a `(<key>, <value>)` tuple with the key being a tuple of the elements and `?` representing the empty set/null value:

```
((1, ?, 6, 3), "hey")
((1, 5, 6, 3), "hi")
((2, ?, ?, ?), "hello")

```

So `lookup((2, 4, 5, 6)) -> "hello"`. And `lookup((1, 5, 6, 3)) -> "hi"` because `(1, 5, 6, 3)` is more specific than `(1, ?, 6, 3)`.

A simple solution is to store them as shown above and simply look through them. This would take $O(nm)$ where $n$ is the number of entries and $m$ is the number of elements in the key. Checking in most-to-least specific would mean a match could be returned immediately.

This there an approach that could improve this?

Thank you

# Answer
This is the problem of building a data structure for storing rectangles in $m$-dimensional space, so you can answer stabbing queries efficiently.

For instance, if your keys have 4 elements, then we are in $m=4$ dimensions. The key $(1,5,6,3)$ corresponds to a single point in 4-dimensional space. The key $(1,?,6,3)$ corresponds to a line in 4-dimensional space. The key $(2,?,?,?)$ corresponds to an (infinite) box in 4-dimensional space.

So, in general, each key can be thought of as an (axis-aligned) box in $m$-dimensional space. A query is a point in $m$-dimensional space, and you want to find all boxes that contain that point. That is sometimes known in the literature as a "stabbing query" (particularly when we're talking about intervals, i.e., $m=1$).

There are many data structures for this problem. Take a look at R-trees, for example. You can also look at $m$-dimensional segment trees. It is known that you can build a $m$-dimensional segment tree in $O(n (\lg n)^m)$ time and $O(n (\lg n)^m)$ space; each lookup can be answered in $O(k + (\lg n)^m)$ time, where $k$ is the number of entries that match the query. Thus, segment trees will likely be a good representation if the dimension $m$ is small. (Optimizations: The exponent can be reduced slightly from $m$ to $m-1$. There are also special algorithms that achieve even better performance in the case of $m=2$, $m=3$, or $m=4$.)

See also Data structure to hold list of rectangles?.
> 3 votes

---
Tags: time-complexity
---


# Question
Title: At what n, does a n^2xn^2 sudoku puzzle take too long to solve?
I'm creating a sudoku solver, and I'm wondering at what point, with a simple backtracking sudoku solving algorithm, does the result take way too long to compute? I'm thinking like more than 30 minutes? I'll probably try to implement some heuristics, but I want to know at what point should I not expect a solution within 30 minutes?

# Answer
> 3 votes
The best way to find out is for you to implementing it and do some experiments.

The difficulty level of Sudoku puzzles varies widely. Moreover, there are many ways to implement a Sudoku solver, and some will be more effective than others on hard Sudoku puzzles (e.g., SAT solvers may be more effective than simple backtracking engines). Therefore, there is no one answer that will be applicable to all Sudoku solvers and all puzzles.

Fortunately, test cases are easy to find. It's easy to find many examples Sudoku puzzles at different levels of difficulty. So, give it a try. On this site, we expect you to do serious research on your own before asking, so before asking here, you should try it on your own. The best way to find out is to try it -- that's something you'll need to do, as we can't do it for you.

# Answer
> 2 votes
Some sudoku puzzles of arbitrary size are easy to solve, for example if every number is given except for $1$ number (that's an extreme example, but the point is that different sudoku puzzles will take different amounts of time to be solved by a given solver). So it sounds like you want to know the worst-case running time for you solver, i.e. find the hardest puzzle for your solver. But we don't know how your solver works, and even if we did, figuring out the hardest puzzle for your solver for each $n$ would be an almost certainly impossible task. There are examples of "hard" sudoku puzzles on the web, but you shouldn't expect them to necessarily be the absolute hardest for your solver. Your question is basically impossible to answer unless you enumerate all sudoku puzzles for each $n$ that have a unique solution and try them all out, in increasing order of $n$ until you finally find a worst-case puzzle that takes more than $30$ minutes to run or whatever your time limit is for your solver.

---
Tags: sudoku
---


# Question
Title: Expected maximum bin load, for balls in bins with equal number of balls and bins
Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we derive this fact? Are Chernoff bounds helpful?

# Answer
The correct approximation here is Poisson. The occupancy of each bin is distributed roughly $P(1)$ (Poisson with expectation $1$), and tail bounds for Poisson random variables show that with probability $1-1/n^2$ (say), the variable is at most $O(\log n/\log\log n)$. A union bound shows that with high probability, all bins contain at most $O(\log n/\log\log n)$ balls.

A good resource on balls and bins is "Balls into Bins" – A Simple and Tight Analysis by Raab and Steger. They use elementary methods to a range of $m$ (balls) and $n$ (bins) that covers the classical case $m = n$.
> 6 votes

---
Tags: algorithms, algorithm-analysis, randomized-algorithms, probabilistic-algorithms, chernoff-bounds
---


# Question
Title: Deterministic Multi-tape Turing Machine construction
I'm trying to construct a deterministic multi-tape turing machine for the following language in order to show that $L$ is in $DTIME(n)$:

$$L = \\{ www \mid w \in \\{a,b\\}^+ \\}$$

I'm not sure how to get started. Any hints would be appreciated.

# Answer
> 0 votes
You could copy the input to 3 tapes, then move the heads on tapes 2 and 3 until they point to the same substring and on tape 3, the end of substring matches the end of string.

The exact steps could be..

> 1. copy input
> 2. erase first symbol on tape two and first two symbols on tape three
> 3. go forward on all tapes until...
> 4. if one of the symbols is different than on other tapes, go back to the start of each tape and return to step 2
> 5. if tape three reaches end of input, you are done

---
Tags: turing-machines, complexity-classes
---


# Question
Title: Matrix equality up to row/column permutations problem name
Sorry for the trivial question; has the following decision problem an "official" (possibly short) name?

> Given two $n \times m$ $\text{0-1}$ (binary) matrices $M\_1, M\_2$ check if they are the same up to row and column permutations.

(something like the short names used in complexity theory for decision problems: e.g. 3SAT, GI (Graph Isomorphism), X3C (Exact Cover By Three Set), CLIQUE, ...)

# Answer
After a few observation in the comments (thanks to Hendrik Jan, Yuval Filmus, and D.W), I post an extended comment as an answer.

It seems (unless I'm missing something) that the problem is equivalent to *Hypergraph isomorphism* (HI):

* to prove that it is equivalent to HI, it is enough to use incidence matrices: every column represents a node of the hypergraph, every row represents an hyperedge (the $1$s are placed on the columns corresponding to the nodes of the hyperedge).

> The question remains valid ... is there a short name for the problem other than Hypergraph Isomorphism (if it appears somewhere not related to graph theory) ?

(if nobody post another answer in a few days I'll temporarily accept mine).

Additional stuff:

* for proving that it is GI-complete it is enough to consider the *incidence* matrix of the source graphs $G\_1, G\_2$;
* the reverse reduction is similar to the well known reduction from HI to GI: it is enough to consider the incidence matrix of the source hypergraphs $H\_1, H\_2$, transform them to graphs: every column becomes a node $c\_i$, every row becomes a node $r\_i$; an edge $(c\_i,r\_i)$ is added if and only if the corresponding cell contains a $1$; and finally a new triangle is linked to every set of nodes $\\{c\_{i\_1},...,c\_{i\_m}\\}$ that represents an hyperedge to preserve hyperedge mapping.
> 2 votes

---
Tags: terminology, reference-request
---


# Question
Title: Complexity of general polynomial map evaluation is polynomial?
A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}\_p$, $x^{p-1} = 1$ for all $x \neq 0$, and is $0$ on $0$, we have that there are a finite number of polynomial maps in $\Bbb{Z}\_p\[x\_1, \dots, x\_k\]$. For now let's work in $\Bbb{Z}\_2$ for simplicity.

The coefficients are arbitrarily chosen $c\_i \in \Bbb{Z}\_2$, and polynomials are in $\Bbb{Z}\_2\[x\_1, \dots, x\_k\]$. Then

$c\_0 + c\_1x\_1$ obviously has complexity $2$ (2 operations explicitly required).

$c\_0 + c\_1x\_1 + c\_2 x\_2$ needs $4$ ops.

$c\_0 + c\_1x\_1 + (c\_2+ c\_3 x\_1) x\_2$ needs $6$ ops max.

$c\_0 + c\_1x\_1 + c\_2 x\_2 + c\_3 x\_3 + c\_4 x\_1 x\_2 + c\_5 x\_1 x\_3 + c\_6 x\_2 x\_3 + c\_7 x\_1 x\_2 x\_3 = \\ c\_0 + x\_1(c\_1 + x\_2 (c\_4 + c\_7 x\_3) + c\_5 x\_3) + x\_2 (c\_2 + c\_6 x\_3) + c\_3 x\_3$

needs $14$ ops. The pattern seems to be

$1 + (k + (k-1) + \dots + 1) + ((k-2) + (k-1) + \dots + 1) + \dots + 1$ which is $O(k^3)$, so is polynomial complexity polynomial?

Where did I make any mistake? Thanks.

This doesn't make sense as there are about $p^k$ coefficients, and each one must be visited.

$\* + x\_1(\* + x\_2(\* + x\_3(\* + \*x\_4) + \*x\_3 + \*x\_4)) + x\_2 (\* + x\_3(\* + \*x\_4) + \*x\_4) + x\_3(\* + \*x\_4) + \*x\_4$

# Answer
You are basically doing an induction definition on $k$, where you evaluate a polynomial in $k+1$ variables by evaluation two polynomials of $k$ variables (by removing $x\_1$.) So you have that the complexity $f(k+1)\approx 2f(k)$, which doesn't look polynomial to me.
> 3 votes

---
Tags: algorithms, complexity-theory, polynomial-time, polynomials
---


# Question
Title: Are Java and C# also purely interpreted languages?
I was wondering about the nature of these managed languages i-e since c# and java both are converted into intermediate language and byte code respectively, and are interpreted by their respective runtime(s). So if they are somehow pure interpreted languages then is it feasible to develop any crucial application on these technologies?

# Answer
It depends on what you mean by "crucial", "feasible", and "interpreted." Certainly applications which many people consider to be crucial are written in C# and Java, so in some sense the answer to your question must be "Yes." But we can try to dig a little deeper.

While it is true that Java and C# are both compiled into byte code, in general the byte code is not directly run by an interpreter. Instead it is Just In Time compiled (jited). This means that when you run a C# program, the byte code is compiled into native code and cached by the Common Language Runtime (CLR) (See the documentation for the ngen program for more details). Many times the compilation will remain in cache until the runtime is updated, so the compilation is only happening a single time, when the the app is started for the first time (its a bit more complicated in practice, but you get the idea.)

Theoretically this means that as new optimizations are added to the framework, or as new processor features become available, the application will be automatically re-jited into a "better" executable. This means that, theoretically, the performance of a C# or Java program can be better than a C program compiled for a generic processor.

Typically the applications that C# and Java are unsuitable for are embedded applications and realtime applications. However, this is mostly due to the way that the most common garbage collectors are non-deterministic, and does not have much at all to do with the way the languages are compiled. Additionally, applications that need to use native libraries, or access memory in very specific ways, may encounter performance problems or other obstacles when implemented in C# or Java, due to auto-boxing, pinning, etc. However this has more to do with "managed memory" and safety then with compilation.
> 3 votes

---
Tags: programming-languages, interpreters
---


# Question
Title: 3-coloring a graph with propositional formulas
I am trying to tackle a specific problem so any help would be greatly appreciated:

> Let $G = (V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. A 3-coloring of $G$ is a map $\chi:V\to \\{R,G,Y\\}$ such that if $\\{x,y\\}\in E$ then $\chi(x)\neq \chi(y)$. (Let $R,G,Y$ stand for red, blue, and yellow respectively).
>
> Suppose $n \> 1$ and let $V\_n = \\{0,1,\cdots,n-1\\}$ and let $G\_n = (V\_n,E\_n)$ be an undirected graph with vertex set $V\_n$. For each $i$, $0 \leq i \< n$ let $R\_i,B\_i,Y\_i$ be propositional variables. We can think of $i$ being a node so $R\_i$ says node $i$ has a color of red.
>
> Give a propositional formula $A\_n$ using the variables $\\{R\_i,B\_i,Y\_i | 0 \leq i \< n\\}$ such that $A\_n$ is satisfiable iff $G\_n$ has a 3-coloring. Do this in such a way that $A\_n$ can be computed efficiently from $G\_n$ (e.g. don't define $A\_n$ to be $R\_1$ if $G\_n$ has a three coloring and ($R\_1 \wedge \neg R\_1$) otherwise).

My inclination for a question like this is to set up some sort of CNF formula, that is come up with a set of clauses that set out to take care of different properties. For instance I believe for something like this I need a clause that deals with the case that every node has a color, maybe one that deals with every node cannot have more than one color, and that every node cannot be the same color as an adjacent node? I am not really sure how to illustrate that last one or if there are cases that I am missing.

# Answer
Hint: Try to formalize the following:

1. Every node has at least one color.
2. Every node has at most one color. (This is actually not necessary.)
3. Any two adjacent nodes cannot have the same color.

Another hint:

> The first can be formalized as $R\_i \lor B\_i \lor Y\_i$ for all $i$.
> 1 votes

---
Tags: logic, propositional-logic
---


title: Card-buying algorithm

text:
# Question
Title: Card-buying algorithm
I'm trying to make an algorithm to calculate what combination of cards from what buyers I should get to get the cheapest deal. Taking the shipping costs into consideration. It's for a website called MagicCardMarket, which is kind of an Ebay for trading cards. The problem is that the site doesn't have a proper optimization tool, so I'm trying to make it myself. (I found some other site that does this, but you have to pay for it and I'm learning a lot already doing it myself.)

The first thing I do is gather a bunch of information. The most important parts being how many and what cards the buyer want. Then I gather all the articles that comply with these cards and throw away all the bad ones (those who's quality is too bad, or language is incorrect, ...) Articles are basically instances of those cards being sold, with info about their seller and cost. So now I have a list of cards, and for each card a list of articles for those cards, and for each article a cost and seller (and from this seller I can get the shipping cost, this can depend on how many cards are bought from a single seller, though most of the time it stays almost constant.)

So now I'm looking for an algorithm to get all the cards you want, as cheap as possible. Taking into consideration that when I buy from more sellers, the shipping cost will go up.

Are there any algorithms I should look at, that might lend themselves to this problem very nicely? Or perhaps some general tips for these kinds of algorithms? It's the first time I'm trying to make this kind of algorithm, so I wasn't sure what to search for either.

The easiest way would probably be to just get all possible combinations, and check which is the cheapest, though most cards will have several hundreds of articles associated with them, and most of the time you'll have 60 to 80 cards you want to buy (a full deck.) So I don't think this is a good way, it uses enormous amount of ram and takes a lot of time. I'm also writing it as a web-app, preferably something that can also work on mobile phones.

Thanks a lot!

PS. I wasn't sure if this is the proper forum to ask this, please redirect me if I was wrong.

# Answer
If you want to solve this in practice, I would suggest that you formulate it as an instance of integer linear programming (ILP).

You can have a variable $x\_i$ for each article that is one if we buy the $i$th article, or $0$ otherwise. Now you get some constraints. For instance, if I want 2 of the Dreadlord card, and they're offered in the 3rd, 7th, and 8th articles, then I get the constraint that $x\_3+x\_7+x\_8 \ge 2$. The objective function is your total cost. You want to minimize your total cost, subject to the requirements.

Here's how you can model the total cost. The only tricky bit are the shipping costs. For simplicity, assume that the shipping cost from a seller is fixed no matter how many items you buy from that seller. To help with modeling the shipping costs, introduce a variable $y\_j$ for each seller, where $y\_j=1$ if you buy anything from the $j$th seller and $y\_j=0$ otherwise. Now use the "logical OR" construction from here to relate the $y\_j$'s to the $x\_i$'s. For instance, suppose that articles 4, 5, and 9 are from seller 2. Then you add the linear inequalities $y\_2 \ge x\_4$, $y\_2 \ge x\_5$, $y\_2 \ge x\_9$, $y\_2 \le x\_4 + x\_5 + x\_9$, $0 \le y\_2 \le 1$. Do this for each seller. Now, the total cost is $$\sum\_i c\_i x\_i + \sum\_j c'\_j y\_j,$$ where $c\_i$ is the per-item cost of the card in the $i$th article and $c'\_j$ is the shipping cost of the $j$th seller. This is the objective function that you're going to try to minimize.

Then, throw an off-the-shelf ILP solver at the resulting set of constraints.

This problem is likely to be NP-hard, so in principle there might not be any efficient solution... but in practice ILP solvers are surprisingly good, so I bet they'll give you a pretty good solution to your problem.

---

Possible complications and details: If the seller has multiple copies of a card available, we need to modify the above. You can have $x\_i$ count the number of them that you buy from that seller (instead of being 0 or 1). Also, we need to modify the construction of the $y\_j$'s, as follows. For instance, if article 5 is from seller 2, and article 5 offers up to 17 copies of the Dreadlord card, then instead of $y\_2 \ge x\_5$, you should use $17 y\_2 \ge x\_5$ (this ensures that if $x\_5 \ge 1$, then $y\_2$ is forced to be $1$).

If the shipping cost is not constant per seller, then you might need a more complex model of the cost. However, here's one simple case that you can handle without difficulty. Suppose that the shipping cost for seller 2 is \\$3 plus \\$0.50 per card ordered. Then you can treat this as a fixed shipping cost of \\$3 (regardless of how many cards are ordered), and increase the per-item cost of each card offered by that seller by \\$0.50. If the shipping cost is a non-linear function of the number of cards bought, then you might need something fancier: in that case, you might want to ask a follow-up question about how to model that specific nonlinear function, and specify the nonlinear fucntion. Or, you could approximate the shipping cost by a linear function and solve the ILP problem anyway, to get something that might be close to optimal, even if your model isn't perfect.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?
I've googled this problem somewhat pretty extensively, and all the relevant literature understandably deals with 2-d or 3-d cases, rather than the n-d case.

EDIT: Yes, ℝn. I've done many searches combining terms like union, intersection, volume, convex hulls, polytope, etc. I've come across papers like this and this. My math and CS background is weak, but I can tell from the latter paper that this is a difficult problem that I am after.

I appreciate both answers given, unless I misunderstand (probable), I'm not sure that they answer my question? The first answer is just about finding the volume of a polytope given its facets or vertices. I'm aware of algorithms to do so. The second answer may be more on track, but it still raises the question of how to determine IF two polytopes intersect, and where?

Thanks, everyone, for your help so far.

# Answer
> 1 votes
Terminology:

* polytope: the object we're talking about, it has dimension N.
* face: a polytope of dimension N-1.
* intersection (point): a polytope of dimension N-2
* edge: a polytope of dimension N-3 Edge
* volume: quantity in units^N representing encompassed space

In principle it's the same deal in any dimension.

1) find intersecting faces and replace them with segmented versions

2) procedurally delete all faces and points that are not part of the union (start with faces that are connected to faces whose inside face is facing an outside face)

3) calculate volume with the irregular volume algorithm (subtract dimension-facing from non-dimension facing)

In detail:

**1) Intersectiong faces.**

A polytope of dimension N will have faces of dimension N-1 and intersection points of dimension N-2.

If ABC ZYX are two 2-polytopes AB and ZY intersect

we find the intersection I by equating the line through AB to the line through BC two times 0=ax+by+c

The new segments would be AI, BI, ZI, and YI.

If ABCD and ZYXW are two 3-polytopes ABC and ZYX intersect

we find the intersection IJ by equating the plane through ABC to the plane through ZYX two times 0=ax+by+cz+d

and delimiting it by its intersection with the segments AB, BC, AC, ZY, ZX, ZX, and choosing the two inside points of the four valid points (1-2-3-4, 2 and 3 are inside points, 1 and 4 are outside points)

the contour line of all line segments can then be used to cut up the faces by various means, such as grabbing the intersegment corners and drawing segments to the surface corners (without segment (e2) overlap)

If ABCDE and ZYXWV are two 4-polytopes ABCD and ZYXW intersect

we find the intersection IJK by equating the space through ABCD to the space through ZYXW two times 0=ax+by+cz+dw+e

and delimiting it by its intersection with the planes ABC, ACD, BCD, ABD, ZYX, ZXY, ZYW, ZXY, YXW, and choosing the three inside segments of the six valid segments (draw up possible polytopes and check whether all points not in the polytope are contained, these other points are your intersection segments)

the contour plane of all plane segments can then be used to cut up the bodies by various means, such as grabbing the intertriangle corners and drawing segments to the body corners (without triangle e3 overlap)

If ABCDEF and ZYXWVU are two 5-polytopes ....

If A and B are two N-polytopes and some $X=\subset A$ intersects with some $Y=\subset B$ we find the intersection I by equating $\Sigma\_{i=0}^{N} dim\_i quant\_i$ of X and of Y, and delimit it by the innermost intersection with the valid permutations of X and Y (which should be half of all intersections).

As you can see it's recursive.

**2) deciding which faces are extraneous**

Assign an extra quantity to each face maybe to decide whether it's facing in the direction of its normal or not. If the segmented neighbors' normals cross (or reach a minimum (they should cross)) behind the direction of the normals, then one of the two needs to go. use a hidden variable process (such as systems of equations) to figure out which after you've crosschecked the entire neighborhood. then you can either keep all faces attached to "essential faces" or delete the disjoined ones.

**3) irregular volume algorithm**

you should know this: take a face and its projection on one axis, and calculate its volume. add or subtract it from the total volume depending on whether the normal (modified by its modifier) points to or away from the axis.

# Answer
> 2 votes
A standard approach is to decompose it into a bunch of triangles (well, the n-dimensional generalization of triangles), then compute the volume of each triangle and sum them up. Have a look at https://mathoverflow.net/q/979 or https://scicomp.stackexchange.com/q/2881. Be warned that this could take exponential time.

There are also algorithms for approximating the volume of such a polytope, if that is useful to you.

---
Tags: computational-geometry
---


# Question
Title: Proving a language (ir)regular (standard methods have failed)
I'm currently trying to prove a language regular (for personal amusement). The language is:

*The language containing all numbers in ternary that have even bit-parity when encoded in binary.*

Now, I've currently tried a few different approaches that have not led me to any success. I've tried using the pumping lemma (couldn't find anything to pump on), Myhill-Nerode (similar) and even counted the number of strings of each length for which the statement is true (my intuition is that it checks out with a probabilistic argument).

Are their any other approaches that might help here, or are there any intuitions that might be helpful? At this point, my best guess is that the language is not regular, but I don't seem to be able to come up with an explanation.

# Answer
> 10 votes
This can be proven, but you need some nontrivial tools to do it.

Start with the set S = {0,3,5,6, ...} of non-negative integers having an even number of 1's in their base-2 expansion.

It is well-known that this set is "2-automatic"; that is, there is a finite automaton accepting exactly the base-2 expansions of elements of S. Furthermore, it is well-known that this set is not ultimately periodic (that is, it is not true that there exists a period P such that after some point C, if x \>= C is in S then so is x+P). (If it were, then the associated Thue-Morse word 01101001... would be ultimately periodic, but it is known from Thue's 1912 paper not to contain any block repeated three times consecutively.)

Next, assume S is actually "3-automatic"; that is, there is an automaton accepting exactly the base-3 expansions of elements of S. Then by a classic theorem of Cobham (Math. Systems. Theory 3 (1969) 186-192, this would imply that S is ultimately periodic. But we have already seen it isn't.

You can find a lot more about these ideas in my book with Allouche, "Automatic Sequences". Warning, though, our proof of Cobham is a bit flawed, and a corrected version by Rigo can be found online here: http://arxiv.org/abs/0907.0624 .

---
Tags: formal-languages, regular-languages, arithmetic
---


title: Small-step semantics: for-loops

text:
# Question
Title: Small-step semantics: for-loops
I'm trying to construct the small-step semantic rules involving the for-loops, but I can't find anything about it in the literature (only about while-loops).

I was wondering if anyone could help me out with this? This is a first attempt, where $s$ represents a statement and $e$ an expression:

$\quad \displaystyle\sigma, \text{for } s\_1 \\, e\_1 \\, e\_2 \\, s\_2 \\, \rightarrow \\, \sigma, \text{if } e\_1 \text{ then (} s\_2 ; \\, e\_2; \\, \text{for } s\_1 \\, e\_1 \\, e\_2 \\, s\_2 \text{ ) else } skip$

Where $\sigma$ is a local value store, $s\_1$ is for example $i = 0$, $e\_1$ could equal $i \< 4$ and $e\_2$ $i=i+1$.

# Answer
> 5 votes
Your attempt does not work. Note that $s\_1$ is never executed. (And if you prepend the right-hand side with "$s\_1;$", it will be executed multiple times.)

What you can do is to translate the for loop into an equivalent while loop:

$$\sigma,\text{for } s\_1, e\_1, e\_2, s\_2 \text{ endfor} \to \sigma, s\_1; \text{while } e\_1 \text{ do } s\_2; e\_2 \text{ endwhile}.$$

---
Tags: formal-languages, programming-languages, semantics, operational-semantics, small-step-semantics
---


# Question
Title: Why is the Boolean hierarchy contained in the class $P^{NP}$?
My textbook says: "The Boolean hierarchy is contained in the class $P^{NP}\subseteq\Sigma^P\_2\cap\Pi^P\_2$." However, it provides neither a proof nor a proof sketch nor some hint. How can I convince myself that the claim is true?

# Answer
> 3 votes
Every language in the Boolean hierarchy can be written as a "Boolean formula" whose "variables" are languages in NP, e.g. $$ \overline{(L\_1 \cap L\_2) \cup L\_3}. $$ Given an oracle to NP (i.e., an oracle to some NP-complete problem) and an input $x$, we can decide in polytime whether $x \in L\_1$, $x \in L\_2$, $x \in L\_3$. We need polytime since NP-completeness is defined with respect to polynomial time reductions. Given the values of the "variables", it is easy to compute the "formula".

---
Tags: complexity-theory, complexity-classes, oracle-machines
---


# Question
Title: Is Simon's problem a good NP-intermediate candidate?
We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$ (Though we have the proof that BQP $!=$ BPP with an oracle)

Since Simon's problem (as factoring) it's easily solvable by a quantum computer, and in exponential time complexity solvable by a classical computer, that's a hint of the separation between BQP and BPP and therefore this can be a pure NP problem. Am I right?

# Answer
> 4 votes
Simon's problem is not a pure NP problem, for two reasons:

* It is an oracle problem. We are given an oracle for some function $f$. That's not something that you can do within the definition of a NP problem.
* It is a promise problem. We are given the promise that $f$ will satisfy a particular property (it is two-to-one, and has a particular structure). That too is not something you can do within the definition of a NP problem.

So Simon's problem is not a problem in the formal complexity class NP; it's just something different. For the same reasons, it's not NP-intermediate, either.

---
Tags: complexity-theory, complexity-classes, quantum-computing
---


# Question
Title: Alternate definitions of enumeration machines
In my textbook, enumeration machines are defined as possessing a special write-only output tape, which they can write characters to, but not move the head of. When they hit the print state, the string on the output tape is enumerated and reset to a blank tape.

Is this equivalent to the model of enumeration machines where they have just one tape, the contents of which is enumerated (but not cleared) whenever they hit the print state? One direction seems easy, but I'm not sure how to prove you wouldn't need the extra tape.

# Answer
Multitape machines are equivalent to single tape machines. You can simulate several tapes on a single tape. In particular, in order to simulate the "print state" model using the "write-only output tape" model, you simulate an extra output tape, and whenever the print state is reached, you copy the contents of the extra output tape to the write-only output tape. Therefore both models are equivalent.

More generally, all reasonable Turing machine models are equivalent. This is a special case of the Church–Turing hypothesis.
> 3 votes

---
Tags: turing-machines, enumeration
---


# Question
Title: Do you know of a brute-force algorithm for optimizing polynomial expressions?
For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$.

Thanks!

# Answer
> 4 votes
"Brute-force" in the context of factoring polynomials may involve factoring of integers, which is a hard problem. Factoring polynomials is easier, e.g. look up "FACTORING MULTIVARIATE POLYNOMIALS VIA PARTIAL DIFFERENTIAL EQUATIONS" by Gao, and "Factoring Multivariate polynomials over the integers" by Wang and Rothschild.

---
Tags: polynomials
---


# Question
Title: Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?
Let the following datatype be defined:

```
 data T = A | B T | C T T

```

That is, `B, B T, B (B T), C A A, C (B T) A` and so on all are members of T. Now, suppose we define two functions that operate on that type:

```
f :: T -> T
f A = A
f (B x) = B (B (f x))

g :: T -> T
g A = A
g (B x) = B (B (B (g x)))

```

There are restrictions on the definition of `f` and `g`: first, recursive calls can only be applied directly to a subterm of one of the inputs (guaranteeing termination), and second, they can't use any datatype other than T on their bodies (consider T is the only existing type). In this case, we know that the following function:

```
h :: T -> T
h A = A
h (B x) = B (B (B (B (B (B (h x))))))

```

works as the composition `f . g`. My question is, is it possible/decidable to find the composition of `f` and `g` in this form - that is, without any reference to `f` and `g` themselves? What is the name of the problem I am trying to solve?

# Answer
If the functions are sufficiently well-behaved, as in your example, you can express `f` and `g` as regular transducers for trees. Then you can compute the composition of two such transducers, which will also be a regular transducer (I believe), and convert it back to a Haskell function.

Another approach: in some cases, simple `let`-substitution might suffice. For instance, given your `f` and your `g`, we can identify their composition `fg` via the following sequence of steps. We know `fg = f . g`, so plugging in the definition of `g`, we get:

```
fg A = f(g(A)) = f A
fg (B x) = f(g(B x)) = f(B (B (B (g x))))

```

Now plugging in the definition of `f`, we get:

```
fg A = A
fg (B x) = B (B f(B (B (g x))))

```

Continuing to plug in the definition of `f`, we get:

```
fg A = A
fg (B x) = B (B (B B( f(B (g x)))))

```

And plugging in the definition of `f` once more:

```
fg A = A
fg (B x) = B (B (B B( (B (B (f(g x))))))

```

which simplifies to

```
fg A = A
fg (B x) = B (B (B (B (B (B (fg x)))))

```

And now you have your desired recursive definition of their composition. Notice that this is the same as the function `h` you wanted to get out. As far as I know, there's no guarantee that this procedure will always work, but it is easy enough to apply.
> 1 votes

# Answer
> What is the name of the problem I am trying to solve?

This is a form of supercompilation.
> 0 votes

---
Tags: algorithms, complexity-theory, computability, programming-languages
---


# Question
Title: FOL substitution - is it possible to substitute two variables with each other? e.g. $\theta=\{x/y,y/x\}$?
Let $C = m(P,X,Y) \leftarrow m(Q,X,Z), m(R,Z,Y)$.

Is it possible to do the following substitution?

$D = C\theta$ where $\theta = \\{Q/R,R/Q\\}$ s.t. $D = m(P,X,Y) \leftarrow m(R,X,Z),m(Q,Z,Y)$

# Answer
> 2 votes
Given the usual substitution function $\[x/y\]$ s.t.

> $M\[x/y\]$ is the result of substituting all free occurrences of '$y$' with '$x$' in $M$,

your desired function can be defined as follows:

> $M \[x//y\] =\_{df} M\[x'/y\]\[y/x\]\[x/x'\]$ provided $x'$ doesn't occur in $M$.

*Example.* Let $C = m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)$. Then:

\begin{align\*} D &= C~\[Q~//~R\]\\ &= \[m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)\]\[Q'/R\]\[R/Q\]\[Q/Q'\] \\ &= \[m(P,X,Y)←m(Q,X,Z),m(Q',Z,Y)\]\[R/Q\]\[Q/Q'\]\\ &= \[m(P,X,Y)←m(R,X,Z),m(Q',Z,Y)\]\[Q/Q'\]\\ &= m(P,X,Y)←m(R,X,Z),m(Q,Z,Y) \end{align\*}

---
Tags: logic, first-order-logic, logic-programming
---


# Question
Title: Fast algorithm to find points on one side of hyperplane?
Given $n$ points $x\_1, x\_2, ..., x\_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm

(1) Preparation: first take the n points as an input, do whatever preprocessing necessary.

(2) Query: for each query $f\_i = w^\top x$ being a hyperplane and a constant $b$, find the subset of points $\\{x\_i | w^\top x\_i \geq b\\}$.

such that the asymptotic complexity for the query is less than $\Theta(k \cdot n)$ ?

# Answer
> 4 votes
The keywords you may be looking for are *simplex range searching* and *half-space range searching*. See chapter 16 of Computational Geometry: Algorithms and Applications. If you are interested in general simplices (intersections of multiple half-planes), then there are two data structures in particular that might interest you: partition trees and cutting trees.

In the following paper describing partition trees, we have query time of $O(n^{1-1/d}(\log n)^{O(1)})$, preprocessing time of $O(n \log n)$, and space requirement of $O(n)$.

Matoušek, Jiří. "Efficient partition trees." Discrete & Computational Geometry 8.1 (1992): 315-334.

In a cutting tree, you consider the dual case (each point in your input is represented by a line in the dual plane) and you tradeoff space for query time. You get $O(\log n)$ query time at a cost of $O(n^{2+\epsilon})$ space.

However, if you really only care about a single half-plane in your query, you can do better. In The Power of Geometric Duality, Chazelle gives an optimal data structure for half-space range queries with $O(\log n + k)$ query time and $O(n)$ space.

# Answer
> 2 votes
This is a bit of a stretch, but you can compute the arrangement of hyperplanes corresponding to $w \cdot x\_i = w \cdot x\_j$ for all pairs of points $x\_i,x\_j$ in your set I believe in in $O(n^{2k-1})$ time. Google arrangements of hyperplanes to confirm the details. For sure you can compute the arrangement of hyperplanes in $O(n^{O(k)})$ time assuming $k$ is a constant. Then for each full-dimensional cone $C$ in the arrangement of hyperplanes, you get a unique ordering on the points induced by all functionals in the cone $C$. Let $w(C)$ be the centroid vector of the generators of the cone $C$. Then it's not absolutely guaranteed, but given a weight vector $w$ the ordering induced by $w$ should be very close to the ordering induced by $w(C)$ where $C$ minimizes the distance between $w$ and $w(C)$ (assuming all vectors are normalized to have length $1$). Thus, for large $n$ compared to $k$, you can build a range tree out of the centroids $w(C)$ and find the nearest neighbor to a query vector $w$ in $O((\log n)^{k-1})$ time assuming $k$ is a constant. Once you know the closest $w(C)$, you automatically have the ordering of points induced by weight vectors in $C$ precomputed, so you can binary search to find the last point in the ordering that satisfies $w \cdot x \geq b$. This takes $O(\log n)$ time (again assuming $k$ is a constant). Overall time complexity is $O((\log n)^{k-1})$, which for large $n$ compared to $k$ beats $O(n)$. Note the ordering might be slightly off though if $w$ lies in a cone $C$ whose centroid $w(C)$ is not the closest centroid to $w$. However you can prove that the true cone $C$ is either the cone that contains $w$ or it is a neighbor of the cone that contains $w$. So if your points are in general position, then at most your computed set of points that satisfy $w \cdot x \geq b$ will be off by one point.

However, I must confess that even in dimensions $k=3$ or $4$, this seems like an awful lot of preprocessing time and storage (computing the entire arrangement of hyperplanes and then building a range tree out of every cone centroid) just to get the complexity down to $O((\log n)^{k-1})$. Especially the storage requirements for the range tree. Also if $k \> \log n + 1$ then the complexity is already worse than $O(n)$. So you need $n$ to be exponential or greater in $k$.

---
Tags: algorithms, complexity-theory, computational-geometry
---


# Question
Title: How to determine if a state is a fixed point in a Hopfield network?
I have been reading a lot and I am still unsure of how to determine this. Let's say I have an initial binary state vector (1, 1, 1). How would I go about determining whether (1, 1, 1) is a fixed point in the network?

My initial understanding was to put the state through the network and if it converged to (1, 1, 1) then it is a fixed point. However I have a feeling it is not as simple as that.

Thanks.

# Answer
> -1 votes
Your intuition is right. A state is a fixed point in a Hopfield network if it is a local minima of the energy function. In other words, some binary state vector $x$ is a fixed point if and only if every other state vector at hamming distance $1$ from $x$ has higher energy. The simplest way to determine if a state is a fixed point is to iterate over each dimension of the state and try to update it. If the state doesn't change then it is a fixed point.

Edit: Too long for comment.

I think you might be confusing *global* and *local* minima. If you take some state (binary vector) $\mathbf{x} = (x\_1, \ldots, x\_n)$, and iterate the dynamics of the network until nothing changes$^{1}$, you will have converged on a fixed point, call it $\mathbf{x}^\prime$. This $\mathbf{x}^\prime$ is a local minima of the energy function. By definition this means that every state at hamming distance 1 (those that differ by 1 bit) will have higher energy. If this was not the case then there exists some $i \in \\{1,\ldots,n\\}$ such that flipping position $i$ in $\mathbf{x}^\prime$ would give a state with lower energy. But this means when choosing to update bit $i$, you would have flipped it$^2$.

Now, what this doesn't mean is the that this is the *global* minima of the energy function. There could be a state that differs by 2 bits from $\mathbf{x}^\prime$ with lower energy. But you can never reach it from $\mathbf{x}^\prime$ by updating a single bit/unit at a time. So you are trapped at $\mathbf{x}^\prime$, in a local minima of the energy function.

\[1\] This is important, you need to make a full pass over all the postions in the state vector without anything changing to ensure you have converged to a fixed point.

\[2\] The relation between the energy function and the dynamics of asynchronously updating units is what makes Hopfield networks interesting. The idea that we can say something global about the network (the energy function) based on local interactions is neat.

# Answer
> -1 votes
It's as simple as that. Write out the state equation. Substitute the state vector. Verify that equality holds. If it does, then you have a fixed point.

Note that what you're calling a state vector probably isn't one in the typical definition of that term. The vector of neuron *inputs* is usually called the state vector. It would be unusual (though of course not impossible) for this to be all 1's.

If what you actually have is the *output* vector, then you can solve for the state vector using the feedback function. Then verify the resulting state vector is consistent with the outputs. If so, then you have a fixed point.

---
Tags: neural-networks
---


# Question
Title: Wagner Fischer Algorithm and the Empty String
In the Wagner Fischer algorithm to calculate the Levenshtein distance for two input strings, the first step is to compare each input string with the empty string for each input. Why is this step necessary? Is the purpose simply to keep the algorithm consistent when checking the strings for matches and mismatches to determine the distance between two prefixes?

Thanks!

# Answer
The Wagner–Fischer is a dynamic programming algorithm. You can think of a dynamic programming algorithm like a recursion. Every recursion needs a base case (like in induction). In this case, the base case is prefixes of length zero. We could also use prefixes of length one as a base case, but the simplest implementation of the algorithms starts with prefixes of length zero.

The prefix zero case can actually happen, for example when both strings have disjoint sets of letters.
> 2 votes

---
Tags: algorithms
---


title: Chomsky normal form: epsilon rule

text:
# Question
Title: Chomsky normal form: epsilon rule
I have pretty simple question, but still can't find an answer just googling it.

I'm trying to understand Chomsky Normal Form (CNF). There are three production rules:

1. $A \to BC$
2. $A \to \alpha$
3. $S \to \epsilon$

First two I understand. But last one $\epsilon$ doesn't makes sense for me. Why do we need this rule? What is use of having this?

# Answer
> 4 votes
The last rule is necessary for languages containing $\epsilon$. A context-free grammar in which $S$ does not generate $\epsilon$ can be converted to Chomsky normal form without the rule $S \to \epsilon$. Conversely, simple induction shows that all other rules do not generate $\epsilon$, so this rule is needed for languages generating $\epsilon$.

The rule arises during the $\epsilon$-elimination step. For each non-terminal generating $\epsilon$, we "optionally" delete it from any production containing in in the right-hand side, and continue the process inductively (eliminating one non-terminal overtly generating $\epsilon$ may reveal that under generates $\epsilon$). Finally, it could happen that $\epsilon$ is pushed all the way to the starting symbol $S$; there is no way to eliminate it there.

---
Tags: formal-grammars, context-free
---


# Question
Title: Clock page replacement algorithm - Already existing pages
When simulating the clock page replacement algorithm, when a reference comes in which is already in memory, does the clock hand still increment?

Here is an example:

With 4 slots, using the clock page replacement algorithm

Reference list: 1 2 3 4 1 2 5 1 3 2 4 5

Initial list would look like this:

```
-> [1][1]
   [2][1]
   [3][1]
   [4][1]

```

The next reference to insert would be 1, then 2. Would the hand still point at 1 after 1, and after 2 ? In other words, after inserting the 5, would the clock look like this :

```
-> [5][1]
   [2][0]
   [3][0]
   [4][0]

```

?

# Answer
I think this example can clarify all your doubts.

For example:
Assumes main memory is empty at the start page reference sequence is:
`3 2 3 0 8 4 2 5 0 9 8 3 2` one reference bit per frame (called the "used" bit)

```
  P   U   3    P   U   2   P   U   3   P   U   0   P   U   8   P   U  4
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|   | 0 |*   | 3 | 1 |   | 3 | 1 |   | 3 | 1 |   | 3 | 1 |   | 3 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|   | 0 |    |   | 0 |*  | 2 | 1 |   | 2 | 1 |   | 2 | 1 |   | 2 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|   | 0 |    |   | 0 |   |   | 0 |*  |   | 0 |*  | 0 | 1 |   | 0 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|   | 0 |    |   | 0 |   |   | 0 |   |   | 0 |   |   | 0 |*  | 8 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
|   | 0 |    |   | 0 |   |   | 0 |   |   | 0 |   |   | 0 |   |   | 0 |*
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+----

  P   U   2    P   U   5   P   U   0   P   U   9   P   U   8   P   U  3
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
| 3 | 1 |*   | 3 | 1 |*  | 5 | 1 |   | 5 | 1 |   | 5 | 1 |   | 5 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
| 2 | 1 |    | 2 | 1 |   | 2 | 0 |*  | 2 | 0 |*  | 9 | 1 |   | 9 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
| 0 | 1 |    | 0 | 1 |   | 0 | 0 |   | 0 | 1 |   | 0 | 1 |*  | 0 | 1 |*
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
| 8 | 1 |    | 8 | 1 |   | 8 | 0 |   | 8 | 0 |   | 8 | 0 |   | 8 | 1 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+---+
| 4 | 1 |    | 4 | 1 |   | 4 | 0 |   | 4 | 0 |   | 4 | 0 |   | 4 | 0 |
+---+---+    +---+---+   +---+---+   +---+---+   +---+---+   +---+----

  P   U   2    P   U
+---+---+    +---+---+
| 5 | 1 |*   | 5 | 0 |
+---+---+    +---+---+
| 9 | 1 |    | 9 | 0 |
+---+---+    +---+---+
| 0 | 0 |    | 2 | 1 |
+---+---+    +---+---+
| 8 | 0 |    | 8 | 0 |*
+---+---+    +---+---+
| 3 | 1 |    | 3 | 1 |
+---+---+    +---+---+

* = indicates the pointer which identifies the next location to scan
P = page# stored in that frame
U = used flag,
0 = not used recently
1 = referenced recently

This is called linear scanning algorithm or Second chance algorithm, used in BSD Linux.
Generally it is implemented as a circular queue.

```
> 9 votes

# Answer
If a reference arrives for a page already in memory, then the replacement algorithm doesn't get invoked at all.

The clock replacement algorithm is trying to achieve some of the benefits of LRU replacement, but without the massive overhead of manipulating the LRU bits on every page hit.

A page can be in one of three states:

1. Present in memory and the `recently-used` bit is `true`. In this case there will be no page fault when an access happens to the page, so no bits will change.
2. Present in memory but the `recently-used` bit is `false`. In this case the page is also marked in the page table in such a way that if the page is accessed a page fault will occur. (And if the page fault occurs in this case, the only thing the page fault handler does is change the state to `recently-used`.)
3. The page is not present in memory. In this case we look at the `clock-hand`. While the `clock-hand` is pointing to a page with the `recently-used` bit set `true` we flip the `recently-used` bit to `false`, and then increment `clock-hand` to point to the next page. When we find a page with `recently-used` already cleared, that is the page we replace. Then we mark the new page as `recently-used` and increment the `clock-hand` to the *next* page.

Clock is, at heart, a probabilistic algorithm for approximating LRU. If the rate at which the page is being accessed is much higher than the rate at which the `clock-hand` is coming back around to the same page then the page has a high probability of being marked `recently-used`. If the rate at which the page is being accessed is low compared to the rate at which the `clock-hand` is coming back around, then the page is more likely to be in state *not* `recently-used`. The most recently-used page will never be replaced. (Why?)
> 8 votes

---
Tags: algorithms, paging, virtual-memory
---