# Question
Title: Analog of PP for computability rather than complexity?
The complexity class **PP** can be defined in many ways, one of which involves randomness - a language $L$ is in **PP** if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2.

I'm curious whether there is a name for the complexity class that can be obtained by relaxing the definition so that the randomized TM doesn't necessarily have to run in polynomial time. Specifically, consider the class of languages $L$ such that there is a TM $M$ where $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2. There is no requirement that this TM halt on all inputs.

Where does this class of problems lie? This class contains **RE** because any recognizer accepts a string $w \in L$ with probability 1 and accepts any string $w \notin L$ with probability 0. I doubt that it's equal to **RE**, though, since I can't see how you could convert this "majority recognizer" for $L$ into an actual recognizer for $L$. I tried placing it somewhere in the arithmetical hierarchy, but I don't see how to encode the concept "more than half of the computation branches accept" into some first-order formula involving alternating quantifiers.

Does this class of problems already exist and have a name? If so, what is it?

Thanks!

# Answer
> 4 votes
"this class of problems lie"s in **RE**, so its name is "**RE**".

$$\begin{align\*}\operatorname{Prob}(M \text{ accepts}) &= \operatorname{Prob}\big((\exists n)(M \text{ accepts after exactly $n$ steps})\big)\\ &=\sum\_n \operatorname{Prob}(M \text{ accepts after exactly $n$ steps})\\ &=\lim\_N \sum\_{n\leq N} \operatorname{Prob}(M \text{ accepts after exactly $n$ steps})\\ &=\lim\_N \\;\operatorname{Prob}(M \text{ accepts in at most $N$ steps}) \\ &= \lim\_n \\; \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\\,. \end{align\*}$$

For all $m$ and $n$ with $m\leq n$, and for all randomness strings $r$, $M$ accepts in at most $m$ steps if and only if it accepts in exactly some $t\leq m$ steps. But then $t\leq n$ so this can only occur if $M$ accepts in at most $n$ steps with randomness string $r$.

For all $m$ and $n$, with $m\leq n$, the probability that $M$ accepts in at most $m$ steps does not exceed the probability that it accepts in at most $n$ steps.

$$\begin{align\*} &\tfrac12 \< \operatorname{Prob}(M \text{ accepts}) \\ &\iff \tfrac12 \< \lim\_n \\; \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\\ &\iff (\exists n)\left(\tfrac12 \< \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\right)\\,. \end{align\*}$$

Therefore, a machine that loops over the positive integers $n$ and accepts if and only if $\tfrac12 \< \operatorname{Prob}(M \text{ accepts in at most $n$ steps})$ will accept exactly the inputs that $M$ has a probability greater than $\tfrac12$ of accepting.

# Answer
> 5 votes
The ideas in this answer come directly from Ricky Demer. I wanted to write a more long-form answer that fills in a few of the details and justifies why this new complexity class is equal to **RE**.

First, let's introduce some notation. Let's call the complexity class described in this problem **PRE** for "probabilistic **RE**." We'll say that a language $L$ is in **PRE** if and only if there is a randomized TM $M$ such that

$$w \in L \leftrightarrow Pr\[M \mbox{ accepts } w\] \gt \frac{1}{2}$$

The question now is how **RE** and **PRE** relate to one another. The goal will be to prove this theorem:

> *Theorem:* **PRE** = **RE**

To prove this, we'll show that each set is a subset of the other. One direction here happens to be relatively easy:

> *Theorem:* **RE** $\subseteq$ **PRE**.
>
> *Proof:* Consider an arbitrary $L \in$ **RE**. Since $L$ is in **RE**, there must be a TM $M$ that recognizes $L$. Specifically, for any string $w$, if $w \in L$, then $M$ accepts $w$, and if $w \notin L$, then $M$ does not accept $w$. Now, we can construct a randomized TM $M'$ that's basically the same as $M$; it doesn't actually use any randomness. As a result, if $w \in L$, then $Pr\[M \mbox{ accepts } w\] = 1$ and if $w \notin L$, then $Pr\[M \mbox{ accepts } w\] = 0$. Consequently, $L \in $ **PRE**.

The other direction of implication is the harder one. We're going to show that if you start with an arbitrary **PRE** language, you can prove that it's also an **RE** language. Equivalently, we'll show how to start with a randomized TM $M$ meeting the criteria of **PRE** and then show how to construct a recognizer for it.

Let $$M$$ be any randomized TM. Our goal will be to prove the following key lemma:

> *Lemma*: $Pr\[M \mbox{ accepts } w\] \gt \frac{1}{2}$ if and only if there is some $n \in \mathbb{N}$ where $Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}\] \gt \frac{1}{2}$

For now, let's assume the lemma is true. This gives rise to an elegant way to build a recognizer for any **PRE** language. Counting up from $n=1$, exhaustively list all computation paths through $M$ whose length is at most $n$ and explicitly compute the probability that $M$ accepts within $n$ steps. If at any point we find that this probability is greater than 1/2, by the lemma we know that the overall probability that $M$ accepts is greater than 1/2, so the input string $w$ must belong to $L$.

On the other hand, suppose that we never find an $n$ for which the acceptance probability within $n$ steps is greater than 1/2. That means that the acceptance probability for each computation length is at most 1/2. Since

$$Pr\[M \mbox{ accepts } w\] = \lim\_{n \rightarrow \infty} Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}\]$$

we would conclude that $Pr\[M \mbox{ accepts } w\] \le \frac{1}{2}$, meaning that $w \notin L$. In other words, the TM that just brute-force checks the acceptance probability for each computation length would be a recognizer for $L$, and so we'd see that **PRE** $\subseteq$ **RE**.

Everything hinges on this key lemma, so let's see how we might go about proving it. One direction is easier. Let's argue that if $Pr\[M \mbox{ accepts } w\] \gt \frac{1}{2}$, then there must be some $n$ such that $Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{steps}\] \gt 1/2$. As mentioned above, we know that

$$Pr\[M \mbox{ accepts } w\] = \lim\_{n \rightarrow \infty} Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}\]$$

Therefore, if we assume that $Pr\[M \mbox{ accepts } w\] \gt \frac{1}{2}$, we know that

$$\lim\_{n \rightarrow \infty} Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}\] \gt \frac{1}{2}$$

We can use the formal definition of a limit to conclude from this that there must be at least one $n \in \mathbb{N}$ such that $Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}\] \gt \frac{1}{2}$.

For the other direction, we need this additional result: if $m \le n$, then

$$Pr\[M \mbox{ accepts } w \mbox{ within } m \mbox{ steps}\] \le Pr\[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}\]$$

Intuitively, this says that the acceptance probability as a function of the length of the computations considered is nondecreasing. Why is this? If you run a computation for $m$ steps and then continue to run it for one more step, all of the branches that were already accepting are still accepting. If none of the new branches exposed by running the TM for one more step are accepting, then the new acceptance probability is the same as the old acceptance probability. If any of the new branches exposed are accepting, the acceptance probability goes up.

Given this, we can say that if the acceptance probability after some number of steps $n$ ever exceeds $\frac{1}{2}$, then the acceptance probability for all larger numbers of steps also exceeds $\frac{1}{2}$, so the limit of the acceptance probability is also greater than $\frac{1}{2}$.

To summarize:

* **RE** $\subseteq$ **PRE** since any recognizer fulfills the conditions of a randomized TM for a **PRE** language.
* If we have a randomized TM meeting the requirements for a **PRE** language, then that TM accepts a string with probability greater than one half if and only if after some finite number of steps the acceptance probability exceeds one half. We can then build a recognizer for the language by simulating branches of the randomized TM and checking, at each point, whether the acceptance probability is at least one half.

Hope this helps!

---
Tags: complexity-theory, computability, complexity-classes, randomness
---


title: Decidability language, intersection

text:
# Question
Title: Decidability language, intersection
I have two langages $ A, B \in \mathrm{coRE}$. How can I prove that $ A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\\,$?

# Answer
The language $A = \Sigma^\*$ is coRE. Since $A \triangle B = \overline{B}$, the statement you are trying to prove implies RE=coRE, which is known to be false: for example, the set of all programs that halt is in RE but not in coRE.
> 1 votes

---
Tags: computability, closure-properties, semi-decidability
---


# Question
Title: Finite Automata -- Determine if a set is regular
I have been at this for hours. The question is:

> Prove that the language $A = \\{0^kx \mid k \> 0, x \in \\{0,1\\}^\*, \text{ and } \\#(0,x) \geq k\\}$ is regular,
>
> where $\\#(n, x)$ denotes the number of $n$ in string $x$.

So far, I have used the pumping lemma to determine that the opposite is not regular, i.e. that if $\\#(0,x) \leq k$, the language is not regular.

I have also constructed a nondeterministic finite automaton that I thought I could use to prove that this set is regular since that is generally the way to go about proving regularity. I can't really draw it, but at start state $s$, if $0$ is read in, then move to state 1 (or state $'0'$). If a $0$ is read in, either stay in state 1 or move to state 2. If a $1$ is read in, move to state 2. However, I honestly don't know what to do further.

# Answer
Hint: Show that a word belongs to $A$ iff it starts at $0$ and contains at least one more $0$. That is, $A$ is accepted by the regular expression $01^\*0(0+1)^\*$.
> 2 votes

---
Tags: formal-languages, regular-languages, finite-automata
---


# Question
Title: If P = NP, why does P = NP = NP-Complete?
If `P = NP`, why does `P = NP` also then equal NP-Complete?

I.e. Why would it then be the case that `P = NP = NP-Complete`?

Assuming `P != NP` , there were problems in NP not in NP - Complete. When `P = NP`, all NP problems are actually now P.

Shouldn't there still be `P = NP` problems not in NP - Complete?

# Answer
> 4 votes
If $P=NP$ then every non-trivial language $L$ is NP-hard, where non-trivial means that $L$ is neither the empty language nor the language of all words. This follows immediately from the definition of NP-hardness (exercise!). In particular, every non-trivial language in NP is NP-hard, and so NP equals NPC plus the two trivial languages.

---
Tags: complexity-theory, np-complete, complexity-classes, p-vs-np
---


# Question
Title: Voronoi diagram algorithm with non-euclidean metric
Do you know any easy to implement algorithm for constructing a Voronoi diagram from a given set of points on a surface, using some different metric (taxicab, for instance)? It can be some modification of Fortune's algorithm.

# Answer
> 4 votes
It depends on the metric and your sites. There is a framework called **abstract Voronoi diagram** that allows you to compute Voronoi diagrams for *well-behaved* instances. In order to define what *well-behaved* means you have to give certain guarantees for the bisecting curves defined by your sites and your metric (for example two such curves intersect only in a finite number of points). The exact requirements might differ slightly depending on the paper you read.

If your problem is a abstract Voronoi diagram, then you can compute it with (a variant) of the *randomized incremental construction* due to Clarkson and Shor - see for example here. Then everything boils down to computations with the bisecting curves.

Note that there is quite some literature about these Voronoi diagrams and also recent progress has been made. I would advice you to go through this.

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


# Question
Title: How a reduction can help up solve a problem?
I am studying the basics of Computation Theory and I came up with an example I can't understand.

Let's have a language $L = \\{\langle M\rangle \mid L(M) = \Sigma^{\ast} \\}$, so $L$ contains codes of all Turing machines which generate all the words from $\Sigma^{\ast}$. It's been said that we can reduce $H$ (the halting problem) to $L$, so $H \leq\_m L$. A mapping $f(\langle M, x\rangle) = \langle N\rangle$ was defined, where $N$ is a Turing machine coded as shown below:

```
N(y):
    if (M(x) accepts):
        accept
    reject

```

Now my problem is: I thought that if $H \leq\_m L$ then if we could solve $L$, we would be able to solve $H$ as well. By this I supposed that if we have a TM deciding on language $L$, we would be able to build a TM deciding on language $H$. But as for me, the machine above does not help me solve $H$ at all. It acually looks like if we could solve $H$, then we could solve $L$, but I can only see the machine above generate $\Sigma^{\ast}$, but not decide on it.

If any of my intuition is correct, a Turing machine $M\_L$ deciding on $L$ would work like: take the code of another Turing machine $M\_A$ and accept if $M\_A$ generates all words from $\Sigma^{\ast}$ or reject when $M\_A$ does not generate all words from $\Sigma^{\ast}$. How would this machine help me build a Turing machine deciding on the Halting problem?

# Answer
> 5 votes
This is a natural trap that almost everyone falls into when encountering this style of reduction for the first time - you have your logic inverted, but in an understandable way.

To start with, note a couple of things:

1. If $N$ accepts at least one string, it accepts every string, so $L(N)$ is either $\emptyset$ or $\Sigma^{\ast}$, nothing in between.
2. $\langle N \rangle$ is an encoding of a Turing Machine, and what we want to know is whether we can decide if $\langle N \rangle$ is in $L$ or not.

So the argument is by contradiction. Imagine that we did have a TM $X$ that decided $L$, then we could give it $\langle N \rangle$ and, as it *decides* $L$, it would say, correctly, $\mathrm{Yes}$ or $\mathrm{No}$.

But if it says $\mathrm{Yes}$, then we know that $M$ halts on $x$, because that's how we built $N$, and similarly if it answers $\mathrm{No}$, $M$ doesn't halt on $x$.

So having $X$ (i.e. being able to decide $L$) allows us to decide the Halting Problem, and hence we have a contradiction.

Note that we're not trying to 'run' $N$, we're asking if there can possibly be an $X$ that looks at $\langle N\rangle$ and says something about it (for every $N$).

---
Tags: turing-machines, reductions, halting-problem
---


# Question
Title: How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?
Say I have a set of 3-CNF clauses $$\mathcal{S} = \\{ x\_1 \vee x\_2 \vee \bar{x\_3}, ~~x\_4 \vee x\_5 \vee x\_6\\}$$

where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$.

How many satisfying assginments are there for $S$? In general, how many satisfying assignments are there for $S$ is the size of $S$ is k?

This is a question about what is a satisfying assignment for 3-disjunctive clause as much as it is about counting. For example when I just have $C = x\_1 \vee x\_2 \vee \bar{x\_3}$, there are $2^3 = 8$ possible assignments: $$1 1 1\\ 0 1 1 \\ 1 0 1\\ 1 1 0\\ 1 0 0\\ 0 1 0\\ 0 0 1\\ 0 0 0 $$ But which one of these are satisfying assignments?

# Answer
As you noted, for every clause there are $2^3$ possible assignments. Exactly one of them does not satisfy the clause: it's the one that has false for all variables that appear in the clause as a positive, and true for the variables that appear as a negative. In your example it is $001$. The rest of the assignments satisfy the clause. Therefore there are $2^3 - 1 = 7$ satisfying assignments for each clause, which means there are $7^k$ possible assignments in total.
> 2 votes

---
Tags: satisfiability, 3-sat
---


# Question
Title: Turing machine working only with 1's and blanks - how to encode input?
Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input?

My approach was that we can rewrite our input tape with unary coding and symbol-codings separated with blanks. If we had, for example, an input

```
...[][]0123[][]...

```

we could try to encode 0 as `1[]`, 1 as `11[]` and so on. We would know when we reached the end of our input word when we read two blanks in a row. However, rewriting the example string from above would cause some problems. When we code a single symbol with multiple ones, we overwrite another symbols and need to remember them in state. In the example above, after encoding 0 our tape would be like

```
...[][]1[]23[][]...

```

And in our state we'd remember that we need to encode 1 now. Hovever, writing the encoding would overwrite 2, 3 and a blank, so we would need to remember those ones as well in the state. Such an approach leads to creating a lot of states: for n-letter alphabet and unary encoding I proposed it would be $(n+1)^n$ (all possible combinations of symbols on n+1 positions on the tape) "basic states", and for each of those we'd need a few more so that we could write an adequate number of "1" finished by a blank. I am not sure if this is acceptable at all.

Is my approach correct? What other approaches could I take?

# Answer
In the following, I use "0" to denote a blank cell, and I first assume that 1 is not used in the original alphabet. I will deal with this at the end.

**A first solution is possible if you assume that the head can go over a cell and read it without writing on it.**

If you assume that you can tell the two ends of your input, the answer to your question is just that you copy/translate the input to unary form on some other part of the tape, so that you do not run the risk of erasing a part of the input that has not been copy/translated yet. If you copy/translate the input from left to right, you start the copying on some part of the tape that is on the right of the original input.

For that purpose, you need markers, and you can for example use 010 to mark the place where you copy the translation of the next symbol. You can erase original symbols as you copy them, and possibly also mark the last erased symbol with 010 (wich you then do not use as translation of an original symbol). Part of the control is teh used to move bertween the two 010 marks during the translation phase.

**But** *you cannot make the number of states dependent on the length of the input*. The TM uses the same finite state control independently of input size, which implies not changing th number of states.

**If you do not allow reading a cell without overwriting it**, things are more complicated. I further assume that the head is initially on the left side of the input. In ordr to make a copy translation without destroying the input, one has to start from the left, and make the copy further on the left.

Since it is impossible to foresee how much space will be needed, the trick is to copy/translate the input into a mirror image, so that it grows on the left, and never risk erasing the original input.

Then you can either decide to compute with a mirror image, or you can just make a second pass on the copy/translated input, so as to reverse it again and have it in the right order.

**Using 1 in the original input.**

I think that it is possible to do the same when 1 is used in the original alphabet. But one must be very careful not to confuse its use in the original input, and in the copy part. This can be done with a specific configuration appearing only a fixed number of times in the created copy, the rightmost one dentifying precisely the beginning of the rest of the original input to be copied.
> 3 votes

---
Tags: turing-machines, encoding-scheme
---


# Question
Title: Fast polynomial calculation over $\mathbb{Z}_{487}$
Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}\_{487}$, I'd like to choose distinct values $x\_0, x\_1, . . . , x\_{242} ∈ \mathbb{Z}\_{487}$, such that I'll be able to calculate $a(x\_j )$ for all $j = 0, . . . , 242$ by calculating three polynomials $a \_0 (x), a\_1(x), a\_2(x)$ of degree at most $80$ for $81$ different values of $x$.

So first of all I divided $a(x)$ into sub-polynomials, simply by: $$\begin{align\*} a(x)=x^{162}\cdot&\left( a\_{242}\cdot x ^ {80}+...+a\_{163}\cdot x+a\_{162} \right)+\\ & x^{81}\cdot\left( a\_{161}\cdot x ^ {80}+...+a\_{82}\cdot x+a\_{81} \right)+\\ &\left( a\_{80}\cdot x ^ {80}+...+a\_{1}\cdot x+a\_{0} \right)\end{align\*}$$

Now I have shown that $2^{243} = 1 \mod 487$, and that for every $1\leq a \leq 242: \\,\\,\\, 2^a \neq 1 \mod 487$.

I wanted to use this so that I can choose distinct $x\_i$ by $x\_i=2^i \mod 487$ for all $0\leq i \leq 242$. Now I thought taking triples, and for that I had two ideas:

1. Choose triples $x\_i,x\_{i+1},x\_{i+2}$ for each $0\leq i\leq 242$ such that $i = 0 \mod 3$.
2. Choose triples $x\_i,x\_{i+81},x\_{i+162}$ for each $0 \leq i \leq 80$.

In any case, given a trio, I wanted to calculate only $a\_2(x\_i), \\,a\_1(x\_i), \\,a\_0(x\_i)$, and then using them to calculate $a(x\_i),\\,a(x\_{i^{'}}),\\,a(x\_{i^{''}})$, where ${i^{'}} $and ${i^{''}}$ will be the next in my trio (depending on which idea to choose).

The problem is, I either got confused and all that's left is obvious, or I just can't seem to make those last few steps. If Im on the right way, can someone help me here? Or perhaps I should choose other trios? Or if not, maybe there's a hint that can help me out?

# Answer
You can very efficiently compute $a(x\_j)$ for each of those 243 values of $x\_j$ by simply evaluating $a(\cdot)$ using Horner's rule. The running time is 243 evaluations of $a(\cdot)$, and each evaluation requires 243 modular multiplications and 243 modular additions. That's a total of $243^2 \approx 2^{16}$ modular multiplications. Consequently, the total running time will be extremely efficient, even without trying to split this into three polynomials $a\_0(x),a\_1(x),a\_2(x)$.

If you want a more efficient method, a better approach is to use a Discrete Fourier Transform. You can use a DFT over $\mathbb{Z}\_{487}$ to evaluate $a(x)$ at 256 different points in running time that's asymptotically $O(n \lg n)$, where here concretely $n = 256$. \[Alternatively, you could use the Number-theoretic transform for $\mathbb{Z}\_{487}$ to evaluate $a(x)$ at $486$ points, and do all your calculations in $\mathbb{Z}\_{487}$.\]
> 4 votes

---
Tags: number-theory, polynomials
---


title: Bellman–Ford negative path meaning

text:
# Question
Title: Bellman–Ford negative path meaning
In the Bellman–Ford algorithm, what is the practical meaning of having a negative path between routers? I have tried searching the net but didn't find any data

thanks Eli

# Answer
> 3 votes
In the context of network routing, negative-weight edges are meaningless.

Bellman–Ford is just an algorithm for finding lowest-cost paths in a weighted graph. The algorithm itself doesn't know or care what the vertices, edges and weights mean: it just finds paths. Interpreting those paths is for the user.

# Answer
> 1 votes
It depends on the innterpretation of the graph, not the algorithm. For example, if you have a deck of cards and have a graph to represent possible exchanges, the weights of the vertices may mean the price you need to pay to exchange. In such case, negative weight of a route between some nodes would mean you are paid more than you pay for such a chain of exchanges.

The algorithm is just to find the shortest paths, it has nothing to do with the interpretation of your graph. What you may mean is that another popular shortest-paths algorithm, which is Dijkstra's, can not handle negative weights, and Bellman-Ford can (it will not hang or return incorrect values). But still this is a separate topic from the interpretation of negative path weights.

---
Tags: graphs, shortest-path, routing
---


title: Is 0* decidable?

text:
# Question
Title: Is 0* decidable?
I found a statement (without explanation) that a language $A = 0^\*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite string of 0's? I also thought that maybe we could create an enumerator that would create all words from $0^\*$ with increasing length, but I am not sure if we can.

So is $0^\*$ a decidable language? And if so, why?

# Answer
$0^\*$ is the set of finite strings consisting only of $0$. There are no possibly infinite strings in $0^\*$. It is trivially regular because the regex $0^\*$ accepts exactly $A$ by definition. All regular problems are computable so we can definitely create a Turing machine for it (look up NFA's and DFA's for more info on the connection of Turing machines to regular languages).

This is just a confusion in what is meant by Kleene closure. If you look here you can see that it is the union of all strings of length 1, 2, 3, ... and so on for all natural numbers. Infinity is not a natural number so there are no strings of infinite length in $A$.
> 22 votes

# Answer
The kleene star of a language $L$ is defined as \begin{align} L^\star = \\{ w \mid w = \epsilon \text{ or } w = w\_1\circ w\_2 \circ \ldots \circ w\_k, \text{ where } w\_i \in L \text{ and } k \in \mathbb{N} \\}. \end{align} Thus there is no such thing as an infinite string of $0$'s in the language $0^\star$, only strings of zeros of arbitrary length.

We can easily construct an DFA that accepts the language $A$: it has only one state $s$, which is both start and end state, and one transition $(s, 0) \mapsto s$. Therefore the language $A$ is regular and also decidable.
> 10 votes

---
Tags: formal-languages, computability
---


# Question
Title: How can I keep track of the state of a sequence after rotating parts of it multiple times?
Given a sorted array

```
1 2 3 4 5 6 7 8

```

and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the right by one), leaving the following for N = 3

```
4 1 2 3 5 6 7 8

```

I need to be able to figure out the state of the array, after performing an arbitrary number of these operations.

I've implemented a simple algorithm using `std::rotate` that simulates this behavior, but the problem is that my input data set is too large, and rotating the physical array gets really slow.

I've also tried doing this in a `std::list` (linked list), while keeping a separate array of pointers to every K-th element, so that I could access anywhere in the list in near constant time, while benefiting from the fast removal. This approach requires moving the pointers (or iterators in my implementation) every time I rotate, but since I have less pointers than the actual elements in the array (say 1 pointer per 1000 list elements), this isn't so expensive. All in all, this solution turns out to be about 2 times faster than the vector in some cases, in others it's less fast, but it's still too slow.

I don't need to store the actual array, I only need to be able to compute the value of any element in it. I can see how to do this easily if I only had to do one rotation, where the 0th index would be the rotated element, everything before the rotated element would be shifted one to the right by one and everything on the right side of the element would be kept in place, but I don't see how to keep this up when I do multiple rotations.

One of the possible solutions I found was using interval trees, though this seems rather complex and I'm not sure if it would be more efficient given the high number of rotations needed.

**TL;DR: Given a sequence of the first N natural numbers, perform K rotations and figure out the final state of the sequence.** For the sake of example, set N = 10^6 and K = 10^5.

# Answer
> 1 votes
But the problem here is that the values of the elements do not matter, since the rotations can change the order arbitrarily (actually, I do not understand why they are first sorted).

You want to find an element according to its index in the list, not its value. A way to do that is to keep with each node of the tree the number of list elements (leaves) dominated by its left daughter. Then very simple arithmetics will tell you at each node whether the $n^th$ element of the list is to be found under the left or the right daughter, and you acess it in $O(\log n)$ steps if the tree is properly balanced.

Then the element in inserted at the beginning, which can also be done in $O(\log n)$ steps.

Then you need to rebalance the tree when it gets unbalanced. But there are techniques to maintain balancing.

The same should be possible with skiplist, again relying on some size information to access by index rather than by value.

# Answer
> 1 votes
If I am not mistaken, the complexity is $O(N+K)$, so $O(N)$. Work backwards. If the last rotation is $r\_1$ then this means $r\_1$ is the first element in your list. Keep working backwards and ignore all earlier occurrences of $r\_1$, they do not matter. Now if you find $r\_2$ that is the second element in your list. Continue, ignoring the earlier $r\_i$ values.

When done, copy all remaining values in the order of the original array.

Keeping track of all values seen can be done using a boolean array of size $N$. Seems a little large, but I guess we need to check all $N$ array elements anyhow.

# Answer
> 0 votes
The easiest option is to use Skip List which will give you much better average case complexity. It will be $O(k\log n)$ from what the wiki page says:

Skip list will give you $O(\log n)$ when you query for an item in the average case. Similarly, it gives you $O(\log n)$ in insertion and removal in the average case. Together, this means that the average cost for your operation is $O(\log n)$

* When you use array, the average cost for your operation is $O(n)$ because you have the same probability of $1/n$ for the cost of $0, 1, 2, .. n-1$. The cost all sum to $O(n^2)$ dividing by $n$ giving you $O(n)$.
* When you use linked list with the addition of pointer array to all values, the argument is similar.

---
Tags: algorithms, combinatorics, arrays, permutations
---


# Question
Title: Automata for languages derived from an automaton by number of state visits
My question in response to this answer: what would the finite automata look like for $L\_1$ and $L\_0$ in the answer?

I get how the languages are formed; however, since $M\_L$ cannot remember how many times it has looped, how does $q$ branch off (if it does) into the two different DFAs for $L\_0$ and $L\_1$?

Definitions:

* $L$ = infinite regular language
* $q$ = state within the DFA for $L$, $M\_L$, where $M\_L$ loops
* $L\_1$ = {w in A | $q$ is visited an odd number of times}
* $L\_0$ = {w in A | $q$ is visited an even number of times}

# Answer
Starting with an automaton for $L$ with state set $Q$, starting state $s\_0$, transition function $\delta$, and accepting states $F$, here is how to construct automata $M\_1,M\_0$ for $L\_1$ and $L\_0$. The state set of both is $Q \times \\{0,1\\}$. The starting state is $(s\_0,0)$. The transition function is given by $$ \delta'((s,x),a) = \begin{cases} (\delta(s,a),x) & \text{ if } \delta(s,a) \neq q, \\ (\delta(s,a),1-x) & \text{ if } \delta(s,a) = q. \end{cases} $$ The accepting states of $M\_1$ are $F \times \\{1\\}$, and of $M\_0$ are $F \times \\{0\\}$.

In words, in addition to remember the original state, the new automaton also remembers the parity of the number of times that $q$ has been visited. Acceptance is determined accordingly.
> 2 votes

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: MAX3SAT proof help? Showing that NP = coNP iff MAX3SAT is in NP
For a 3CNF $\phi$, denote by $c(\phi)$ the largest number of clauses satisfied under an assignment. Define:

$\mathrm{MAX3SAT} = \\{\langle\phi, k\rangle\mid c(\phi) = k \text{ and }\phi\text{ is a 3CNF}\\}$.

Prove that NP = coNP if and only if MAX3SAT is in NP.

I've been working on this forever and can't seem to figure out anything. Any help?

# Answer
> 1 votes
Let's start by describing a polytime reduction $f$ that takes a 3CNF $\varphi$ to another $f(\varphi)$ such that:

1. $\varphi$ is satisfiable iff $f(\varphi)$ is satisfiable.
2. We can always satisfy all clauses of $f(\varphi)$ but one.

The idea is very simple: add a new variable $x$, replace each clause $\alpha \lor \beta \lor \gamma$ with 3CNF clauses equivalent to $x \lor \alpha \lor \beta \lor \gamma$ (i.e. with the clauses $x \lor \alpha \lor \lnot T$, $T \lor \beta \lor \gamma$ for a new variable $T$ appearing only in these clauses), and add the clause $\lnot x$. We can always satisfy all clauses but the last by having setting $x$ and all $T$ variables to true. On the other hand, the entire 3CNF is satisfiable if and only if the original one is.

We deduce that $\varphi$ is unsatisfiable iff $c(f(\varphi)) = |f(\varphi)|-1$, where $|f(\varphi)|$ is the number of clauses in $f(\varphi)$. This shows that MAX3SAT is coNP-hard. So if MAX3SAT is in NP then NP=coNP.

Conversely, as observed by David Richerby, MAX3SAT is in the polynomial hierarchy (indeed, in $\Delta\_2^P$) since $c(\varphi) = k$ iff some assignment satisfies exactly $k$ clauses, and all assignments satisfy at most $k$ clauses. If NP=coNP then the polynomial hierarchy collapses to the first level (i.e. NP), and so MAX3SAT is in NP.

---
Tags: complexity-theory, np-complete
---


# Question
Title: Is Morse code without spaces uniquely decipherable?
Are all Morse code strings uniquely decipherable? Without the spaces,

```
......-...-..---.-----.-..-..-..

```

could be `Hello World` but perhaps the first letter is a `5` -- in fact it looks very unlikely an arbitrary sequence of dots and dashes should have a unique translation.

One might possibly use the Kraft inequality but that only applies to *prefix codes*.

Morse code *with spaces* is prefix code in which messages can always be uniquely decoded. Once we remove the spaces this is no longer true.

---

In the case I am right, and all Morse code message can't be uniquely decoded, is there a way to list all the possible messages? Here are some related exercise I found on codegolf.SE

# Answer
> 98 votes
The following are both plausible messages, but have a completely different meaning:

```
SOS HELP      = ...---...  .... . .-.. .--.        => ...---.........-...--.
I AM HIS DATE = ..  .- --  .... .. ...  -.. .- - . => ...---.........-...--.

```

# Answer
> 39 votes
Quoting David Richerby from the comments:

> Since ⋅ represents E and − represents T, any Morse message without spaces can be interpreted as a string in $\\{E,T\\}^\*$

Further, since A, I, M, and N are represented by the four possible combinations of two morse characters (⋅-, ⋅⋅, --, -⋅, respectively), any message without spaces can also be interpreted as a string in $\\{A,I,M,N\\}^\*\\{E,T\\}?$. Note that for any Morse message of length \> 1, this is distinct from David's interpretation. Thus, the only messages with unique interpretations are those of length 1 (and, I suppose, 0, if that counts as a message) - that is, ⋅, representing E, and -, representing T.

Here's some JavaScript that will tell you all possible interpretations of a string of `.` and `-`. Strings of up to length 22 run in under a second, but anything higher than that starts getting pretty slow - I wouldn't, for example, try to decode HELLO WORLD with it. You can pop open a JavaScript console in your browser, paste this in, and then call, for example, `decode('......-...-..---')`. (In this example, entry #2446 is the intended string "HELLO".)

```
var decode = function(code) {
  var cache = {
    '0': ['']
  };
  for(var start = 0;start < code.length;start++) {
    for(var len = 1;len < 6;len++) {
      if(start + len > code.length) continue;
      if(!cache[start + len]) cache[start + len] = [];
      var curCode = code.slice(start, start + len);
      if(dict[curCode]) {
        for(var i_start = 0;i_start < cache[start].length;i_start++) {
          cache[start + len].push(cache[start][i_start] + dict[curCode]);
        }
      }
    }
  }
  return cache[code.length];
};

var dict = {
  '.-': 'A',
  '-...': 'B',
  '-.-.': 'C',
  '-..': 'D',
  '.': 'E',
  '..-.': 'F',
  '--.': 'G',
  '....': 'H',
  '..': 'I',
  '.---': 'J',
  '-.-': 'K',
  '.-..': 'L',
  '--': 'M',
  '-.': 'N',
  '---': 'O',
  '.--.': 'P',
  '--.-': 'Q',
  '.-.': 'R',
  '...': 'S',
  '-': 'T',
  '..-': 'U',
  '...-': 'V',
  '.--': 'W',
  '-..-': 'X',
  '-.--': 'Y',
  '--..': 'Z',
  '.----': '1',
  '..---': '2',
  '...--': '3',
  '....-': '4',
  '.....': '5',
  '-....': '6',
  '--...': '7',
  '---..': '8',
  '----.': '9',
  '-----': '0'
};

```

The code to prune it to only strings of real words is a bit longer, so I put it here. It runs under node.js and expects a file at `/usr/share/dict/words-2500`. The dictionary I'm using can be found here. It is not naive - it prunes as it goes, so it runs *much* faster on larger inputs.

The dictionary consists of a top-2500 words list I found on the internet somewhere, minus some 1-, 2-, and 3- letter combinations that I deemed not words. This algorithm is sensitive to having too many short words to choose from, and slows down drastically if you allow, say, every individual letter as a word (I'm looking at you, `/usr/share/dict/words`).

The algorithm finishes by sorting based on the number of words, so the "interesting" ones will hopefully be at the top. This works great on `HELLO WORLD`, running in under a second and returning the expected phrase as the first hit. From this I also learned that `DATA SCIENTIST` (the only other phrase I tried) morse codes the same as `NEW REAL INDIA`.

Edit: I searched for more interesting ones for a few minutes. The words `SPACES` and `SWITCH` are morsagrams. So far they're the longest single-word pair I've found.

# Answer
> 17 votes
It is enough to observe that certain short combinations of letters give ambiguous decodings. A single ambiguous sequence suffices, but I can see the following:

```
ATE ~ P
EA ~ IT
MO ~ OM

```

*etc.* As David Richerby notes in the comments, any letter is equivalent to a string of Es and Ts, which makes Morse Code ambiguous as a way of encoding arbitrary sequences of letters; the above combinations show that this is true even of plausible letter combinations in English (for instance, `MEAT` ~ `MITT`). Perhaps an interesting coding exercise would be to find all strings of five or fewer letters which could be mistaken for something else, restricting to letter combinations that may actually be found in English text (using one or more words), grouped by equivalence class.

Using your original example, it also happens to be the case that

```
HELLO WORLD ~ HAS TEAM NO MAID TOE

```

and while the right-hand side is perhaps unrealistic even as a partial message, it is certainly a sequence of English words, and one that could be found in less than 15 minutes without computer assistance. This could be taken as evidence that many phrases in English could be misparsed as a different (possibly nonsensical) sequence of English words.

# Answer
> 11 votes
Morse Code is actually a ternary code, not a binary code, so the spaces are necessary. If spaces were not there, a lot of ambiguity would result, not so much with the entire message, but with individual letters.

For example, 2 dots is an I, but 3 dots is an S. If you are transcribing and you hear two dots, do you immediately write "I" or do you wait until you hear another dot (or dash)?

The answer is that each value is space separated so they are grouped together. When operators key messages in Morse, they make a pause of the same length as a dash after each letter code sequence to indicate the end of the sequence.

Even if you wrote an AI program to look at a full sentence at a time and figure out what was the logical interpretation of the message, there would still be many slight ambiguities and misspellings that would

# Answer
> 5 votes
a few notes not covered in other (good) answers but which dont generally research prior knowledge and *cite* any stuff (to me an intrinsic part of computer *science*).

* this general theory of CS falls into the category of text segmentation and also "word splitting"/ "disambiguation" although there the theory is a bit different, its about splitting sequences of symbols into words (with variable letters), etc, where the symbols are units. here the strings are split into letters where letters have variable length, but the theory is analogous although not exactly 1-1. ie mapping between sentences-into-words, variable-word-letter-lengths, and sentences-into-words, variable-word/letter-lengths.
* as others have pointed out this can be studied empirically. and someone did that from one angle (there are multiple ways to study this) and "published" the results on a web page with a big directory/ table of results.

> I found 25,787 ambiguous Morse code words. This is made of 10,330 distinct Morse strings. The highest frequency ambiguous Morse word has 13 possible donor words. The results are grouped below in tables based on the frequency of words that share the same Morse representation.
* wow, "context matters"... a nearly identical question "translating morse code without spaces" on stackoverflow from 3yrs ago currently has 0 votes.

# Answer
> 2 votes
In general there are exponentially many possible decodings, but if you really want you can list them all. You can also list them in a succinct way, that is, give a succinct representation for all of them. Since this is nothing more than a programming exercise, I challenge you to do it yourself.

That said, the fact that there is ambiguity does not preclude the ability to decipher the message, or at least large parts of the message. Assuming a probabilistic model for the text represented by the Morse code – for definiteness, we can assume that it's English and use statistical properties of English – it may be possible to essentially decode the message, though some local ambiguities may be unavoidable. The reason is that most decodings correspond to non-sense plaintext. The way to do it is to extend the dynamic programming algorithm from the previous paragraph to estimate the likelihood of each decoding, and then choose the maximum likelihood decoding. This approach has more chance to succeed as the message gets longer.

# Answer
> 1 votes
## How to define/recognize/generate the language of all possible decodings.

Clearly, without spaces, the morse code is no longer uniquely decipherable.

It is however possible to give in a condensed form all the possible ways to decode it. This is actually similar to what is done in speech processing: from a unique stream of sounds (or of phonems), you have to find all the ways it can be decomposed in a sequence of words. The algorithms for doing this produce what is called a word lattice. You will find an example in the "lexical ambiguity" section of this answer.

In the case of binary Morse code (no spaces), you have only dots and dashes, but the problem is the same.

The way you can get all translations is as follow.

First you build Generalized Sequential Machine (GSM) $T$ that decodes the a Morse sentence. This is easily achieved by building a trie that recognizes Morse code. When a code is recognized, the corresponding letter/digit is output, and there is (non deterministically) an empty transition back to the root of the trie. But at the same time, the code word may be continued into a longer one (non-deterministically).

Then you take your Morse sequence $w$ of $n$ dashes and dots, and you read it as a linear finite state automaton $W$ with $n+1$ states (the positions between the dashes and dots, from $0$ to $n$) that generates this unique sentence, i.e. the singleton language $L=\\{w\\}=\mathcal L(W)$. What you want is the language of all translations $T(L)$. You know from general theorems that, since L is finite, hence regular, and since regular languages are closed under GSM mappings, that the language $T(L)$ is regular. So what you really want is a FSA that recognizes (or generates) that language.

For that purpose, you can simply apply a standard cross-product construction, similar to the one used for the intersection of two regular languages, to the two finites states devices $T$ and $W$. The transition are chosen so that you mimic both the transducer $T$ and the FSA $W$. **You easily get a FSA that defines the regular language of all translations.**

The details are easily worked out. But ask if you need more.

# Answer
> 0 votes
Some pseudo-code for a solver that will give all possible interpretations. This is based on a few quick thoughts, so additional input would be welcome. Method accepts two inputs one of the text so far translated, and the second of morse code.

```
MorseSolver (string textSoFar, string codeRemaining)
{
    if(codeRemaining length == 0) output textSoFar
    else
    {
        codeLength = length of code remaining
        read 1 through (min of 5 or codeLength) characters from codeRemaining
        for each set of characters
        {
            call an IsMorseCode method that checks if the characters
              input are valid morse code
            if they are valid add the translated character to textSoFar
              and remove the characters from codeRemaining, then call
              the MorseSolver again with the new strings)
        }

}

```

This will output all the possible combinations of letters and numbers without any spaces between "words". If you wanted to prove the ambiguity, this would certainly do it. If you wanted to get some meaningful messages out, then try looking for code meant to translate hashtags into readable language.

Using the above, I wrote a program in C# which does the above. I stopped it from running at 22 million possibilities for the above string that can translate to hello world. The Morse Code equivalent of "Hello" resulted in 20,569 possible results. I also did not include the numbers. That would be higher if I allowed them.

---
Tags: information-theory, coding-theory
---


# Question
Title: How again do certain sorting methods use $o(n \log n)$ time?
I hope this question isn't too 'soft' for here. It's been a while $\tiny{\text{an eternity for some people's standards}}$ since I've touched this stuff, and I had a convincing explanation to this question eight minutes ago but must have misplaced it, so please help me find it again:

Most classical sorting algorithms one reads about are comparison sorts, in which a single comparison produces a binary outcome (let's break ties arbitrarily). The motivation for this I remember is that they are general, requiring only that an ordering be prescribed over the items, and insensitive to how the items are encoded, but suffer from a $\Omega(n \log n)$-time barrier simply for reason of needing to do enough comparisons to distinguish the $n!$ possibilities. One then meets algorithms such as radix sort, which is supposed to beat this under caveats such as the space of items being discrete and bounded, and assuming the ability to retrieve any decimal/etc. place in constant time. But as I recently thought about it, this operation is essentially a $b$-way switch as opposed to the (ordinary) $2$-way kind used in comparison sorts. Then radix sort would be subject to the same lower bound on time taken since the foregoing gives an improvement of $(\log b)/(\log 2)$ (at most?). So how is radix sort ever preferable to one of the standard comparison sorts? I know this is a contradiction, but not how so.

In my experience this kind of paradox typically dissolves when formalised. I would rather have an intuitive reason that explains it away if such is available, though.

# Answer
> 6 votes
Radix sort cannot be reduced to a comparison-based sort. If the alphabet is binary, then in some sense you are doing 2-way comparisons, since each bit is either 0 or 1. If there are $n$ numbers of width $w$, radix sort takes time $O(nw)$. Therefore as long as $w \ll \log n$, radix sort will be faster than any comparison-based sort.

What does the condition $w \ll \log n$ mean? If numbers have width $w$ then they are in the range $0$ to $2^w-1$. When $w \ll \log n$, there are less than $n$ possible numbers, so some numbers repeat. In this regime you can beat comparison-based sorting.

Another algorithm beating comparison-based sorting in the regime in which there are less than $n$ possible number is *counting sort*. Suppose that the domain is of size $m$. We initialize an array of size $m$, and count how many elements of each type there are. We can then unpack this histogram into the sorted array. This runs in time $O(n+m)$. If $m \ll n$ then this algorithm runs in optimal $O(n)$ time.

In both of these cases, the algorithms cannot be rephrased in the decision-tree model (try doing it!), and so aren't subject to the limitations of comparison-based sorting. No paradoxes here.

# Answer
> 5 votes
There is no paradox because the cost definition is different in the two cases. Since you want intuition, one can think about it as counting the cost of going on a trip by the money you pay or the distance you travel or the time you travel. They are different units of measurement.

In comparison sorting, we assume that the cost of comparing 2 numbers is a fixed constant. This is just a simplified assumption for theoretical purposes. Depending on different machine implementations and the way numbers are encoded, it may take more than a constant amount of cost to comparing two numbers.

Think about an implementation where each number is encoded by lot of bits. In this case, the possible numbers in the encoding scheme are bounded by a large area. Clearly, you will need more than 1 unit of cost to do comparison. I believe this is decided by the number of bits in the computer's registers for modern computers.

Even if, as you mentioned, you can do multiple-way comparison, you will need to put the compared numbers in different buckets. If your $b$ in comparison way is too big, you will need to have many buckets at each run to account for how many different buckets a number can fall into.

The running time of radix sort will then be:

* Create 2 sets of $b$ buckets
* Run $n$ numbers for each run

**CORRECTION:** The number of runs is $\frac{N}{n \log b}$ where $N$ is the input size in your encoding scheme. So the total cost is: $\frac{N\ n}{n \log b} = \frac{N}{\log b}$. You can see now that there is no $n$ in this formula. You can't theoretically compare radix sort with comparison sorts.

Now, you can see where I am going. Radix sort will be preferable when your numbers are bounded (ie, their encoding is not too long). The less the encoding is, the less runs you need, the faster the sort will be.

# Answer
> 4 votes
It is preferable if the length of the inputs are less than the the log of the size of the array. For instance if I have 256 buckets and I break integers up into 4 bytes then I need to run 4 passes to sort them properly however $log 16=4$ so there is a potential advantage for arrays of length greater than 16. But really all I've said here if we translate this to asymptotic terms is that there is some size for which radix sort will overtake merge sort. I once wrote a radix sort algorithm in C++ that did just the above. I found it was comparable for inputs less than 10000 but after that started to beat the standard libgcc std::sort. On an array of size 1000000 it beat it quite well. For small inputs (like inputs less than 1000) std::sort seemed to cream my radix sort no matter what I did. I believe this had to do with the fact that insertion sot was being used on the smaller sections.

# Answer
> 4 votes
Let's assume for the moment that the sort keys are all distinct, and think about the information theory of sorting.

An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to discover precisely which permutation it is.

To transmit a number between $1$ and $m$ requires transmitting $\log\_2 m$ bits of information. To transmit a permutation of $n$ elements, therefore, requires $\log\_2 n!$ bits of information. By Stirling's approximation, this turns out to be $n \log\_2 n + O(\hbox{low order})$ bits.

A binary comparison operation discovers one bit of information. It follows that any sorting algorithm which only uses a binary comparison operation must perform $O(n \log n)$ comparisons.

A radix sort beats this by discovering more than one bit per query. If you can discover $\Theta(\log n)$ bits per query, for example, then you can sort using $O(n)$ queries.

**EDIT** The key word in that last sentence is "if".

Suppose that we have $n$ distinct integers, and we wish to radix sort them using $k$ buckets.

Clearly, each query will discover $\log\_2 k$ bits of information. It follows that any such sort must perform $\frac{n \log\_2 n}{\log\_2 k}$ queries (ignoring the low-order term).

If $k = 2$, then this has the same complexity as a comparison-based sort. However, if $k = \Theta(\log n)$, then sorting will be linear. In most cases, $k$ will be somewhere in between these two values.

---
Tags: algorithms, sorting, efficiency
---


title: Proving a function is uncomputable

text:
# Question
Title: Proving a function is uncomputable
I am trying to solve the following problem:

For each Turing machine $M\_k$ and each string $x$ in $\\{$0,1$\\}$$^\ast$ let

$time\_k(x)$ = $\\{$the number of steps executed by $M\_k(x)$ if $M\_k(x)$$\downarrow$ (halts), and $\infty$ if $M\_k(x)$$\uparrow$ (does not halt)$\\}$

Prove that the function $T$: $\mathbb{N}$ $\rightarrow$ $\mathbb{N}$ defined by

$T(n)$ = max$\\{$$time\_k(x)$ | $0$ $\leq$ $k$ $\leq$ $n$, $x$ $\in$ $\\{$0,1$\\}$$^\ast$, and $M\_k(x)$$\downarrow$ (halts)$\\}$

is uncomputable.

So far, I have begun my proof by assuming that $T$ is computable. Thus, there exists a Turing machine $M$ such that for all $n$$\in$$\mathbb{N}$, $M$ produces $T(n)$ on its tape. Thus, we must show that we can decide the Halting Problem if $T$ is computable, which in turn lets us know that $T$ is uncomputable since the Halting Problem is uncomputable.

I do not know where to go from there however. Any help would be greatly appreciated. Thanks in advance.

# Answer
> 0 votes
Hint: Given $T(n)$, any $k \leq n$, and an input $x$, it is enough to run $M\_k$ for $T(n)$ steps in order to decide whether it halts on $x$.

---
Tags: computability, reductions, undecidability, halting-problem
---


# Question
Title: Counting inversion pairs - $n^2$ results in $n \log n$ time?
The number of possible inversions in an array is bounded by $\binom{n}{2}$, i.e $\frac{n(n-1)}{2} \in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(n\log n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/).

# Answer
Swaps that make a permutation are different from the number of inversions. A max of $n\*log\\, n$ swaps define a permutation. An inversion in a permutation occurs anywhere one element is less than another element at a higher position so a reverse sorted list has $n^2$ inversions but the corresponding permutation has about $\frac{n}{2}$ swaps that define it. We just have to undo the swaps to sort something.

If you are familiar with algebra you might look at the symmetric group for more information on this. Specifically a cycle of length 2 is called a transposition and all permutations can be defined by about $n\*log\\,n$ transpositions.
> 0 votes

# Answer
Here is an even more amazing example. The *determinant* of an $n\times n$ matrix is a sum of $n!$ products, yet we can compute it in time $O(n^{2.373})$. Here is another striking example. Given a binary string of length $n$, we can count the number of binary strings of the same length in time $O(n)$ even though there are $2^n$ of them. What limits the running time is not the *magnitude* of the output but its *length*.

In this particular case, the output length is $O(\log n)$, so it provides no meaningful limit at all. Even though there could be up to $\binom{n}{2}$ many inversions, we can count them without listing them all, just as in the example of binary strings. As you mention, there is an $O(n\log n)$ algorithm doing that. It is conceivable that there is an even faster algorithm, though nothing faster than $O(n)$, since you need (in general) to read at least $n-1$ entries of the permutation before you can be sure what the number of inversions is.
> 3 votes

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


# Question
Title: top-N recommendation in collaborative filtering
I have started to read about user-based and item-based collaborative filtering techniques. I understand how a rating of the target user for a particular item is predicted. How top-N recommendation list is created in user-based/item-based collaborative filtering??

# Answer
Apache Mahout has several implementations about this problem. Most common approach is to predict all unrated items of a particular user and sorting items by their predicted values. Then you can select top N items to recommend. (see class AllUnknownItemsCandidateItemsStrategy in Mahout).

A version of this implementation with better performance and low accuracy is SamplingCandidateItemsStrategy. This one does not select all unrated items to predict, instead it selects some of them randomly with a given rate and then predict only these items. Finally you can select best predicted items as usual. Advantage of this method is to predict less items but since you eliminate some items randomly accuracy of this method obviously will be worse.

Moreover, there are other implementations which use item based similarity to select candidate items such as AllSimilarItemsCandidateItemsStrategy, PreferredItemsNeighborhoodCandidateItemsStrategy,

AllSimilarItemsCandidateItemsStrategy finds similar items of the customer's preferred items and predicts this set. It has a better accuracy since you select relevant items for customer but selecting candidate items phase requires effort.

These are some methods which are used generally.
> 1 votes

---
Tags: recommendation-systems
---


# Question
Title: Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?
To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), and to demonstrate that some known NP-complete problem $B$ can be reduced to $A$ (such that we can write $B \leq\_p A$), by *some* kind of appropriate reduction in polynomial time. We can then say that we can solve $B$ in polynomial time with an oracle for $A$.

One famous example of this would be the reduction of 3SAT to 3-coloring.

So sure, I understand that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time. But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT? The 3SAT $\leq\_p$ 3-coloring reduction, of course, requires the use of special and restricted graphs where a 3-coloring exists iff a satisfying assignment for the 3SAT problem exists.

Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP? Might it not be the case that such an algorithm would be worthless for solving families of 3-coloring problems?

Doesn't this imply some kind of hierarchy of NP-complete problems?

(Said a bit differently: If an oracle that allows one to solve a single NP-complete problem in polynomial time must necessarily be an oracle that allows one to solve all NP-complete problems in polynomial time, shouldn't we need to show $B \leq\_p A$ AND $A \leq\_p B$, where $B$ is some known NP-complete problem, to prove that some problem $A$ is NP-complete?)

# Answer
> 5 votes
> But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?

3-SAT is $NP$-complete, by the Cook-Levin theorem. This means that *any* problem in $NP$ (such as 3-coloring) can be solved in polynomial time given an oracle for 3-SAT.

> shouldn't we need to show $Q \leq\_p P$ AND $P \leq\_p Q$, where $Q$ is some known NP-complete problem, to prove that some problem $P$ is NP-complete?

Yes, but you essentially get the $P \leq\_p Q$ for free because $P$ is in $NP$ and $Q$ is $NP$-complete.

# Answer
> 2 votes
> To prove that some decision problem $P$ is NP-complete, my understanding is that it suffices to show that the problem is in NP \[...\] and to demonstrate that some known NP-complete problem $Q$ can be reduced to $P$ \[...\] by *some* kind of appropriate reduction in polynomial time. We can then say that we can solve $Q$ in polynomial time with an oracle for $P$.

This is correct.

> So sure, I understand that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time. But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?

Yes, the converse holds, because 3SAT is also **NP**-complete. But that is a separate fact, which requires a separate proof. Of course, that proof exists: it's typically proven by taking an arbitrary **NP** Turing machine and writing a Boolean formula that says "That machine accepts its input." Indeed *something* has to be proven **NP**-complete by this kind of method. We couldn't claim that *all* problems in **NP** can be reduced to complete problems just by reducing complete problems between themselves: at some point, you do have to prove that all **NP** problems do reduce to some specific complete problem.

To see why don't get the converse for free, consider reductions outside **NP**. Because **NP**$\\,\subset\\,$**NEXP** (nondeterministic exponential time), any problem in **NP** can be reduced to any **NEXP**-complete problem. However, we know that the converse reduction, from a **NEXP**-complete problem to an **NP** problem, cannot exist: that would imply that **NP=NEXP** but we know that those two classes are different, by the time hierarchy theorem.

> The 3SAT $\leq\_p$ 3-coloring reduction, of course, requires the use of special and restricted graphs where a 3-coloring exists iff a satisfying assignment for the 3SAT problem exists.
>
> Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP? Might it not be the case that such an algorithm would be worthless for solving families of 3-coloring problems?

What you (should have!) heard in class is that having a deterministic polynomial time algorithm for 3SAT would prove that **P=NP**. But remember what an oracle is. An oracle is an add-on to your Turing machine with the following property: if you write a 3SAT instance onto the oracle's tape, you can "push a button" and, in one time step, the oracle will tell you whether that formula is satisfiable or not. So, the fact that 3SAT is **NP**-complete means that **NP** is equal to the class of problems that can be solved in polynomial time by a deterministic Turing machine with an oracle for 3SAT. However, that is not **P**: **P** is the class of problems that can be solved in polynomial time by a deterministic Turing machine with no oracle at all. In symbols, you've proved that **NP=P3SAT**, not that **NP=P**.

However, if you can prove that 3SAT is in **P**, i.e., that there is a deterministic polynomial time algorithm (without using oracles) for 3SAT, *then* you have proven that **P=NP**. The reason is that, now, you can go back to your proof that **NP=P3SAT** and replace all the oracle calls with a "subroutine" that just solves the 3SAT instance you wrote to the oracle's tape.

> Doesn't this imply some kind of hierarchy of NP-complete problems?

Not really, no. However, there *is* a hierarchy of **NP**-complete problems. I already alluded to that above by using the time hierarchy theorem to separate **NP** and **NEXP**. But the time hierarchy theorem is a little more powerful than that: it also tells us that **NTIME($n^k$)$\neq$NTIME($n^{k+1}$)**. That is, for all $k$, there are things that you can do nondeterministically in $O(n^{k+1})$ steps that you can't do in $O(n^{k})$ steps (the same is true for deterministic machines). That gives you a hierarchy right away.

In practice, you don't hear about this hierarchy very often. I think the reason is that, by the time you've said that a problem is **NP**-complete, that already means that it's hard enough that you probably don't care about its exact complexity. For deterministic algorithms, we do care about the hierarchy: $\Theta(n^{10})$ is impractical, $\Theta(n^3)$ is OK on smallish datasets, $\Theta(n\log n)$ is great unless you're Google and $n$ is the whole web, etc. But for **NP**-complete problems, they're almost all at the "impractical" end so we normally don't bother to distinguish.

(Footnote for the experts: yes, we often distinguish between **NP**-complete problems in terms of, say, fixed-parameter tractability and the **W**-hierarchy but I think that's not really the direction this question is going.)

# Answer
> 1 votes
A problem $P$ is NP-hard if all NP-problems can be solved with an oracle for $P$ in polynomial time. $P$ is NP-complete if $P$ is NP-hard and in NP.

> So sure, I understanding that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time.

Here, you are showing that 3-coloring is at least as hard as 3SAT: 3SAT can be solved if we know a solution for some special kinds of instances of 3-coloring - but we don't know whether there are instances of 3-coloring that are harder than 3SAT. (A)

Technically, if you already know that 3SAT is NP-hard, this shows that 3-coloring is NP-hard: If you can solve any NP problem with an oracle for 3SAT in polynomial time, you can now solve any NP problem with an oracle for 3-coloring in polynomial time.

> But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT? \[...\] Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP?

You don't need to assume, but you can prove that (1) 3-coloring is in NP, and (2) 3SAT is NP-hard. These two proofs need not be (and most likely are not) similar to the other direction.

These proofs show that 3SAT is at least as hard as 3-coloring: 3-coloring can be solved if we know a solution to some special kinds of instances of 3SAT - but with this alone we don't know whether there exists instances of 3SAT that are harder than 3-coloring. (B)

---

To combine, (A) means that all instances of 3SAT can be solved if we know how to solve some specific instances of 3-coloring, and (B) means that all instances of 3-coloring can be solved if we know how to solve some specific instances of 3SAT. These two *separate* pieces of knowledge tell us that being able to solve all instances of 3SAT is "equivalent" to being able to solve all instances of 3-coloring.

---

The standard method of proving that $P$ is NP-complete.

* Show that $P$ is in NP.
* Pick an NP-complete problem $Q$, for example 3SAT. Because we already know (someone else has proved) that $Q$ is NP-complete, we know that $Q$ is at least as hard as $P$.
* Show that $Q$ can be solved in polynomial time with an oracle for $P$. Now we know that $P$ is at least as hard as $Q$.

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: How to go about proving an algorithm correct?
The algorithm (called as rmax(1,n)) finds the maximum of a list of numbers contained in an array S\[1..n\].

```
rmax(x, y)
// return maximum in S[x..y]
if y − x ≤ 1
then return maximum(S[x], S[y])
else max1 ← rmax(x, [x+y]/2)
     max2 ← rmax([x+y]/2 + 1, y)
     return maximum(max1, max2)

```

How would I go about arguing that the algorithm is correct?

# Answer
To prove the correctness, we have to prove actually the function `rmax(x,y)` returns the the maximum number with index between `x` and `y` in the array `S[1..n]`, provided the hypothesis: `1≤x≤y≤n`.

There is a semantic technique that often works nicely for recursively defined functions such as this one.

Your function can be defined as the least fixed-point of a functional:

```
F = λ rmax, x, y. if y-x≤1 then max(S[x],S[y]) else
                  else max(rmax(x,(x+y)/2), rmax((x+y)/2+1,y))

```

I have changed a bit the style, for convenience. You note that `F` is a function of 3 arguments, and you original function `rmax` is defined as its least fixpoint in the semantic domain. Also, here `rmax` is a local name for the first argument of `F`. I could replace it by any other name (alpha conversion). I kept `rmax` only for readability.

Now, the way you prove correctness is by checking that this functionnal preserves correctness when it is applied to a function `foo` that is correct, when it is defined (it is undefined for example if it does not terminate, but being defined is actually a formal semantic property).

That is, you only have to check that if the function `foo(x,y)` is correct, then the function `F(foo)` is also correct.

```
F(foo) = λ x, y. if y-x≤1 then max(S[x],S[y]) else
                 else max(foo(x,(x+y)/2), foo((x+y)/2+1,y))

```

When `y-x≤1`, we know that either `x=y` or `x=y-1`, since by hypothesis `1≤x≤y`. In both cases we see that `max(S[x],S[y])` is the right answer.

Otherwise, we see that `1≤x≤(x+y)/2≤n` and `1≤(x+y)/2+1≤y≤n`. Hence the hypothesis is verified for the two calls to the function `foo`. So, since the function `foo` is correct by hypothesis, each call (when giving a defined result) returns the maximum array value between the bound given by its parameters (if it is defined). Since both ranges cover the range between `x` and `y`, the maximum of these two values is the maximum value between `x` and `y`.

Note that there is no base case in this recursion. The reason is that it starts using with the totally undefined function $\bot$ (read "bottom"), which is thus always correct when it is defined.

Note that this does not prove termination of the algorithm. But you get that easily by induction.

**Some further explanations.**

This proof is in a way very similar to the proof suggested by Yuval Filmus. It is not too surprising as they are both supposed to prove the same result. However they are quite different in spirit. Yuval's proof is a recursion on the steps of an actual interpretation of the program (operational semantics). The proof I am proposing is by recursion on the structure of the program code seen as an infinite program defined as the limit of an infinite sequence of finite program (denotational semantics). It assumes continuity properties (so that passing to the limit makes sense), which are verified for usual computing operations and predicates.

The former proof is on the use of the program, while the latter is on its structure.
> 2 votes

# Answer
One way to prove the correctness of the algorithm is by induction on $y-x$. First you have to state your induction hypothesis carefully: if $1 \leq x \leq y \leq n$ then $\mathrm{rmax}(x,y)$ returns the maximum of $S\[x\],\ldots,S\[y\]$. When $y-x \leq 1$, you prove it directly. When $y-x \geq 2$, then $\[x+y\]/2-x \< y-x$ and $y-(\[x+y\]/2+1) \< y-x$, and so the induction hypothesis applies to the recursive calls, and from that you can complete the proof. Finally, when $x=1$ and $y=n$, the induction hypothesis implies that the maximum of the entire array is returned.

As Jake mentions, if you want to do this really formally, you'll have to use a more formal framework such as Hoare logic. But usually these frameworks aren't used in earnest, and are best left to computers to deal with.
> 1 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof
---


# Question
Title: Finding three factors of a number with minimal sum
Suppose that we have a number $x \in \mathbb{Z}^+$.

I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum.

Is this problem a variant of subset sum? Am I stuck with an exponential time algorithm?

## Examples

$32 = 4 \times 4 \times 2$
$36 = 4 \times 3 \times 3$
$11 = 11 \times 1 \times 1$
$6 = 2 \times 3 \times 1$

# Answer
The problem does not require exponential time. It can be solved in subexponential, but superpolynomial time.

The first step is to find the prime factorization of $x$, which can be done with the general number field sieve.

Next, enumerate all possible values of $a,b$ and for each tuple $(a,b)$ compute $c$ to find the triple with the minumum sum. A number $x$ has at most $\exp(O(\log x / \log \log x))$ divisors, so there are also at most $\exp(O(\log x / \log \log x))$ such tuples.
> 2 votes

---
Tags: algorithms, factoring
---


# Question
Title: Relation between CLR Grammar and Ambiguity
I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous?

Is it possible that a grammar which is unambiguous can't be parsed using CLR Parser?

# Answer
> 2 votes
A grammar may be may unambiguous, but not parsable by a LR(k) parser. It is actually possible that a language has an unambiguous grammar, but cannot be parsed deterministically by any PDA, hence has no LR(k) parser.

For example the language $\\{a^nb^n\mid n\>0\\}\cup\\{a^nb^{2n}\mid n\>0\\}$. It is clearly unambiguous (it is easy to write an unambiguous grammar for it). But, informally, there is just no way you can decide which way you want to parse before you have read all the $a$ and as many $b$.

An ambiguous grammar may define a language that has another grammar that is not ambiguous, and may even be CLR(1) or LR(0). Actually, you can just take an LR(0) grammar and add a few useless rule to make it ambiguous without changing the language.

However, there are context-free languages that are inherently ambiguous, i.e. that can only be defined by an ambiguous grammar. And of course, there is no way an inherently ambiguous language can be parsed deterministically.

# Answer
> 1 votes
I found the answer. A Grammar if not CLR(1) may be unambiguous... but if a grammar is ambiguous cant be CLR(1) grammar. For details you can consider this paper from stanford.

---
Tags: formal-grammars, parsers, ambiguity
---


title: Programs for artificial system design?

text:
# Question
Title: Programs for artificial system design?
Are there program systems that can discover the need of routines - and then design them, code them and use them as parts of the system?

---

Any group of humans trying to pursue an activity has to develop in a developed system, to solve their problems by formulating the issues, search for knowledge and methods, to be tested and evaluated - and to be incorporated into the common experience for the activity to be pursued. Are there some software that could be compared with a human process like that?

# Answer
There has been a lot of work in genetic programing (GP) in this vein. Automatically defined functions are a big deal in GP and figuring out how many and what kinds of ADF's you should have (the "Architecture") has been the subject of a lot of research as well. More generally some people have looked at how to use GP to create libraries that it can then work with to make new more complex functions.

GP can often create perfect solutions like reversing a list or sorting lists. More often how ever it generates approximate solutions. It is really clever what all it can do however. John Koza (a really big name in GP) used genetic programing to find entirely new circuits that had never been created before and were effectively open problems in electrical engineering. To do this he had it design everything from the ground up but it had many recognizable circuits as sub parts. One could imagine that it might have made these things faster if it had already had those designed parts in its library.
> 1 votes

---
Tags: artificial-intelligence, code-generation
---


# Question
Title: Dijkstra single-source shortest path $\Omega(n\log n)$?
If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case?

I know heaps reduce Dijkstra's algorithm to $Ο(m \log n)$ and can be stored in an array. Rooted, binary, as complete as possible tree with all nodes satisfy Heap property: node \<= all children of node.. Is this the right direction?

\**I have an implementation that runs $O( (n + m)\log n)$, could it work?

# Answer
Let $m$ be the number of vertices and $n$ the number of edges. The best you can get is $O(n + m \log m)$ by using a Fibonacci heap.

A Fibonacci heap allows decreasing the key of an element in amortized constant time. For each edge in the graph, Dijkstra's algorithm executes at most one decrease key operation. All these operations take time $O(n)$ in total. On top of that we have $m$ minimum extractions, which take time $O(m \log m)$ in total. Therefore the final complexity is $O(n + m \log m)$.
> 1 votes

---
Tags: algorithm-analysis, graphs, shortest-path
---


title: What is the overhead of Virtual Memory?

text:
# Question
Title: What is the overhead of Virtual Memory?
What is the price paid for the vast virtual address space provided to programmers for their applications? Or in other words, what is the overhead due to virtual memory?

Is there any other overhead from implementing virtual memory, beyond memory consumed by the kernel?

# Answer
> 2 votes
One major overhead of virtual memory is that virtual pages that are being used in the current computation have to be loaded in physical memory, which usually means also transferring out another page back on disk. Since this is costly, you want to avoid doing it too often. Hence an important concept is the *locality* of programs: though a program may have to use considereable space, you try to organize the program so that only a much smaller part of memory is used at any time, a smaller part that evolves only slowly.

THis concerns the code being executed, but also the data used. And data is often orders of magnitude larger than the code. So, a program handling large amounts of data will often be organized so as to improve the locality of the data organisation in memory (but this depends also on what the code does with the data). As a consequence, too naive a use of classical textbook algorithms may result in very slow programs, because of too many page faults.

I guess there are tools to analyze the locality of programs, or to optimize them to improve it. A specific example is the design of garbage collectors, which have developed various techniques to improve data locality by reorganizing the information, and which are of course design to explore the memory in a very local way, for example by looking in priority at pages the main program has already loaded in physical memory.

Programs with bad locality spend too much time loading pages compared to actual computing time. This is called *thrashing*.

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Does there exist $O(n)$ worst case sorting algorithm for sorting a list of integers?
When I looked on wikipedia, all the sorting algorithms listed have worst case $O(n^2)$.

My question is suppose we are given a list of integers, each of which is in some fixed, finite set (i.e. $\\{-1, 0, 1\\}$). Does there exist a sorting algorithm that sorts this list in $O(n)$ time?

# Answer
> 7 votes
There are some algorithms that could run in $O(n)$, but only for some specific inputs.

In general, if a sorting algorithm is based on comparisons then it will always take at least $\Omega(nlog(n))$ steps. The proof is pretty simple and based on an observation of a tree that contains $n!$ leaves, each one containing some order of $n$ elements to be sorted. You can read more about it here.

There are some sorting algorithms quaranteed to run in $O(nlog(n))$ (merge-sort or heapsort, for example), as well as some that have the worst case $O(n^2)$ (like quicksort). Note that merge-sort also uses $O(n)$ memory and Quicksort uses some memory through recursive calls. Heapsort sorts in place.

However, if your set fulfills some restrictions, then you may have an algorithm that can sort in $O(n)$. If you have to sort a big list of values that come only from quite a small range (by which I mean that the amount of values to sort is much greater than the number of possible values), you can use counting-sort. It will run in $O(n+k)$, where n is the size of your array (or list or whatever else) to sort and k is the number of possible values. For example: let's say you want to sort an array of $n = 10^6$ 8-bit chars. Counting sort would be ideal, as the size of your set of possible values is $k = 2^8 = 256$, and this is much less than 10 million. You can see that your $k$ does not add much to complexity compared to $n$, so you may say that counting sort will sort this in $O(n)$.

Other examples you should look at: radix-sort and bucket-sort are some other algorithms that could sort in $O(n)$ (average case).

# Answer
> 1 votes
I believe this paper gives the closest things to a known sorting algorithm for sorting that list in $O(n)$ time.
That paper's abstract is

> Sorting n integers in the word-RAM model is a fundamental problem and a long-standing open problem is whether integer sorting is possible in linear time when the word size is $\omega(\log n)$.
> In this paper we give an algorithm for sorting integers in expected linear time when the word size
> is $\Omega(\log^2 n \log \log n)$. Previously expected linear time sorting was only possible for word size $\Omega(\log^{2+\epsilon} n)$. Part of our construction is a new packed sorting algorithm that sorts n integers of
> w/b-bits packed in O(n/b) words, where b is the number of integers packed in a word of size w bits.
> The packed sorting algorithm runs in expected $O\hspace{-0.04 in}\left(\hspace{-0.02 in}\frac{n}{b}\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\log n + \log^2 b)\right)$ time.

.

Alternative Links to the Same Paper: ,,

# Answer
> 1 votes
There is no known algorithm that is $O(n)$ in the worst case. However if the numbers are bounded by some constant, i.e. the difference of the largest and the smallest element is less than some constant value, then radix sort works in time $O(n)$.

---
Tags: sorting
---


# Question
Title: How to find a 2-wise independent hash family that is not 3-wise independent?
I'm trying to find a family of hash functions mapping $\\{1, 2, ..., 2^n\\}$ to $\\{0, 1\\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that?

I know two 2-wise independent families but I think they are 3-wise independent as well:

1) Let x be a vector in $\\{0, 1\\}^n$. The hash functions are $h\_{a, b}(x)=a^\top x+b \mod 2$ for all $a\in\\{0, 1\\}^n$ and $b\in\\{0, 1\\}$.

2) Consider $GF(2^n)$. The hash functions are $$h\_{a, b}(x)= \text{the last bit of }a \cdot x+b $$ for all $a, b\in GF(2^n)$.

# Answer
> 0 votes
The smallest example I could find is $$ 0001 \\ 0010 \\ 0100 \\ 1000 \\ 0011 \\ 0101 \\ 0110 \\ 1001 \\ 1010 \\ 1100 \\ 1111 \\ 1111 $$ I'll leave you to generalize this to larger $n$.

---
Tags: probability-theory, hash
---


# Question
Title: Which CNF boolean formulas blow up exponentially at conversion to DNF?
If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa).

But what is an example of such a formula (and is there a general way to capture their structure - if the first question is too easy, and I'm just too stupid to see it)?

In this post, the parity function is discussed as an example of a function which blows up exponentially when converted to both CNF and DNF from a non-NF version: Formulas for which any equivalent CNF formula has exponential length

But what about just CNF \<=\> DNF? And how frequent are these "bad" formulas? (Very rare, I'd suspect, but can it be proved?)

# Answer
> 8 votes
The classical example is $$(x\_1 \lor y\_1) \land (x\_2 \lor y\_2) \land \cdots \land (x\_n \lor y\_n)$$ which blows up to $2^n$ terms when converted to a DNF.

Most functions have CNF and DNF complexity very large – $\Theta(2^n/n)$ if I remember correctly – and so for random functions there is no blow-up for trivial reasons.

Miltersen, Radhakrishnan and Wegener construct a *monotone* function which has an exponential gap.

---
Tags: space-complexity, boolean-algebra
---


# Question
Title: Transforming the sorting problem into Dijkstra
To get a lower bound of nlogn I am taking the sorting algorithm, which is well known to have that, and transforming/adapting it to Dijkstra's single source shortest path problem.

I know you need to do create a graph based on the numeric values and that Dijkstra will traverse it in order, any help with the rest and how to evaluate it? Thank you.

# Answer
> 2 votes
What you want is to reduce sorting (or element uniqueness) to the *single source shortest path* problem (rather than to Dijkstra's particular algorithm!) using an $o(n\log n)$ time reduction whose output has size $O(n)$. Then you will get a tight decision tree lower bound in the algebraic decision tree model for constant degree (Dijkstra's algorithm can be implemented using a linear algebraic decision tree).

Such a reduction is probably not known. See for example D.W.'s question on cstheory.

---
Tags: shortest-path
---


# Question
Title: Proving the lower bound of compares in comparison based sorting
I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help is appreciated!

# Answer
A sorting algorithm using at most $h$ comparisons on all inputs corresponds to a tree of height at most $h$. Such a tree has at most $2^h$ leaves. On the other hand, each permutation of $1,\ldots,N$ must land at a different leaf, and so there must be at least $N!$ leaves. Putting these together, we deduce that $2^h \geq N!$ and so $h \geq \log\_2 N! = \Omega(N\log N)$ (using Stirling's approximation). So every sorting algorithm must use at least $\log\_2 N! = \Omega(N\log N)$ comparisons in the worst case (on some inputs it can use less).
> 16 votes

# Answer
Assumptions:

* The input consists of $n$ values which can potentially be distinct.
* The only way to obtain information about the order of values is to apply a function which compares two values and returns a boolean indicating whether the first value is less than or equal to the second value. (This is what “comparison sort” means.)

Given the first assumption, there are $n!$ possible permutations of the input (i.e. there are $n!$ ways to reorder the input). If a run of the algorithm makes $k$ comparisons, then it can only distinguish between $2^k$ different sets of permutations, since each comparison at most multiplies the number of distinguishable permutations by 2. If $2^k \lt n!$, then by the pigeonhole principle, there exist two permutations of the input which lead to the same state of the program implementing the algorithm. Since the algorithm has to work for inputs where all values are distinct, these two permutations cannot both be in the desired order.

For example, suppose you're sorting $4$ values. There are $4! = 24$ permutations. The first comparison divides the set of permutations into two sets, at least one of which must have at least $12$ elements. All the permutations in a given set are indistinguishable without further comparisons. The second comparison divides the set in two, which in the worst case leaves at least $6$ indistinguishable permutations. Another division reduces the worst case set size to $3$, another one to $2$, and a final one may be able to reduce the set size to $1$, uniquely identifying the permutation.

The upshot is that any correct sorting algorithm under these assumptions must execute a number of comparisons $k$ in the worst case such that $2^k \ge n!$. The number of comparisons is thus at least $\log\_2(n!)$. By Stirling's approximation and a bit of simple calculus, $\\\_log\_2(n!) = \Omega(n \log\_2))$. This proves that a comparison sort has a worst case time complexity lower bound of $\Omega(n \log(n))$, by the number of comparisons alone.

Relaxing either assumption allows faster sorting algorithms. In practice, these assumptions model the reality well most of the time.

* Exercise: suppose that instead of a less-than function returning true or false, we have a binary compare function that returns “less”, “equal” or “greater”. What is the lower bound on the worst-case number of calls to the comparison function? Does this improve the asymptotic bound?
* There are scenarios where the first assumption doesn't hold. For example, to sort a list of values which are all 0 or 1, it's enough to put all the 0's before the 1's, which can be done in linear time. More generally, if there are $n$ values to sort but only at most $p$ *distinct* values, it's possible to sort them in $O(n \log(p))$. Radix sort achieves this. The proof above doesn't apply because it's ok to end up with a set containing multiple potential permutations, if all the permutations only move around values that are equal.
> 5 votes

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


# Question
Title: Creating a one-to-one mapping between a N-length list and M workers?
I have a list of length *N*, and I have *M* workers. I want each of my workers to independently select a contiguous section of the list, with the property that every element of my list is selected by exactly one worker.

Using the SQL notion of `offset` and `limit`, I have an approximation:

`offset = (worker_number / total_workers * list_length).to_i
limit = list_length / total_workers + 1`

The problem is that, for some values of `N` and `M`, this results in overlaps, where some elements are processed multiple times.

Is there a general solution that ensures the one-to-one correspondence between elements and workers, yet allows each worker to independently compute their `offset` and `limit`?

# Answer
Sure. Give the $i$th worker the range of items at indices from $\lfloor Ni/M \rfloor$ to $\lfloor N(i+1)/M \rfloor - 1$.

Here I assume indices range from $0$ to $N-1$, and workers are indexed by $i$, where $i$ ranges from $0$ to $M-1$. Also, the notation $\lfloor x \rfloor$ represents the result of rounding $x$ down to the nearest integer.

This ensures that there are no overlaps, and the list is split evenly among the workers (as evenly as possible: each worker receives either $\lfloor N/M \rfloor$ items or $\lfloor N/M \rfloor + 1$ items).
> 1 votes

---
Tags: algorithms
---


# Question
Title: How can I construct a Turing Machine that accepts encoding of another Turing Machine?
How can I construct a Turing Machine that accepts the language L = \<'M'\> which is an encoding of a Turing Machine M?

# Answer
> 1 votes
Choose a coding of Turing machines such that every string is a valid coding. Then, your Turing machine just needs to accept $\Sigma^\*$, which is trivial.

---
Tags: turing-machines, encoding-scheme
---


# Question
Title: Relationshop between Theta and little-o (Big-O notation)
Is $$ f(n) \in \Theta(g(n)) \Leftrightarrow f(n) = g(n) \cdot (1+o(1)) $$

true?

For clarity, here are the definitions I use: $$ f(n) \in o(g(n)) \Leftrightarrow \forall \epsilon \> 0 \exists n\_o\forall n\> n\_0: |f(n)|\leq \epsilon \cdot |g(n)| $$ $$ f(n) \in O(g(n)) \Leftrightarrow \exists c \> 0 \exists n\_o\forall n\> n\_0: |f(n)|\leq c \cdot |g(n)| $$ $$ f(n) \in \Omega(g(n)) \Leftrightarrow \exists c \> 0 \exists n\_o\forall n\> n\_0: c \cdot |g(n)| \leq |f(n)| $$ $$ f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in \Omega(g(n)) \land f(n)\in O(g(n)) $$

What I have so far:

The $\Leftarrow$ direction is quite easy:

$$ f(n) \in o(g(n)) \Rightarrow f(n) \in O(g(n)) \land g(n)+o(1)\cdot g(n) \in \Omega(g(n)) $$

However, I am unsure about the other direction. I suspect that it's not, but can't proof it.

PS: This is not a homework assignment, but homework related: I am working on a seminar paper and want to understand this.

# Answer
> 1 votes
To expand slightly on Karolis's comment, you can get a counterexample by taking for any strictly positive function $f$ and, for any constant $\delta\>0$, the function $(1+\delta)f(x)$. $(1+\delta)f(x)\in \Theta(f(x))$ but $(1+\delta)f(x)\notin (1+o(1))f(x)$ since, for $\epsilon\<\delta$, it is not true that $(1+\delta)f(x)\leq (1+\epsilon)f(x)$.

---
Tags: asymptotics
---


# Question
Title: Non-deterministic algorithm to check if a list has some given value
I know that I can build a non-deterministic algorithm with a `CHOICE` function that verifies if a value `x` is in an array in O(1) time complexity.

The usual algorithm to do that is

```
find (A, x)
    j = CHOICE(1, .. , A.length)
    if A[j] == x
        return VALID
    return FAIL

```

But, it works because we are able to access the position `j` directly, in constant time.

So, if I change the problem: instead of an array A, use a linked-list L, then, how can I construct my non-deterministic algorithm using the `CHOICE` function to check if a value `x` is in L or not ?

Will it still have O(1) time complexity ?

# Answer
If the only way you have to access the last element is to step through the whole list, one item at a time, you can't possibly use less than $O(n)$ time, even nondeterministically. If you used less than that, none of the paths through the computation would be able to access the end of the list, so none of them would be able to check whether it contained the desired entry.
> 2 votes

---
Tags: complexity-theory, nondeterminism
---


# Question
Title: Asymptotic analysis for quicksort on special case
I have the following problem for homework:

Given an array of the form $\[m+1, m+2,..., n, 1, 2,..., m\]$ as an input, analyze quicksort's run time complexity. TIP: check for $m \> \frac{n}{2}$ and $m \le \frac{n}{2}$

**The quicksort algorithm is the deterministic version from CLRS.**

I have a sense of what's going on but I'm having trouble proving it properly.

I arrived at the following formula: $$\begin{align\*} T(n, m) &= T(n-m, m) + \theta (m^2) + \theta (n) \\ &= \cdots \\ &= T(n-(i+1)m, m) + i\theta(m^2) + \sum\_{k=0}^{i} \theta(n-km) \end{align\*}$$ from the following reasoning:

at each "step" $i$ the partition will swap the $m$ smallest numbers (located at the end of the sub-array) with the next $m$ smallest numbers (located at the beginning of the sub-array), keeping their sorted order. The sub array is of size $n-im$, so the partition takes $\theta(n-im)$. Then perform the first recursive call on the $m-1$ smallest numbers on the left of the sub-array for ~$\theta(m^2)$. Next we perform the next recursive call on an sub-array of size $(n-(i+1)m)$.

We can easily see when this will end with a mod operation. (I understand there is a bit additional work even after we can't sub $m$ smallest numbers anymore but that's not very important so omitted).

Now, my issues are:

1. I don't understand how to treat $m$ and $n$. $m$ is somewhat dependent on $n$ because it cannot grow indefinitely without $n$ growing as well. But on the other hand, it doesn't depend directly on $n$.
2. If I substitute the end condition I get an expression with both $n$ and $m$ which I believe I should find a way to express in terms of $n$ alone but I don't know how.

I know I omitted alot of reasoning, details and formalism but it's got quite long anyhow so I hope it's clear enough. If not, I will be more than happy to clarify.

I'd appreciate any help or suggestions.

EDIT: here is the pseudocode for partition and quicksort:

# Answer
> 1 votes
A more correct recurrence is $$T(n,m) = \begin{cases} T(n-m,m) + \Theta(m^2+n) & m \leq n/2, \\ \Theta(m^2+n) & m \> n/2. \end{cases}$$ In order to solve the recurrence, let us assume that the hidden constants are all $1$, and that $n = km$. Then $$ \begin{align\*} T(km,m) &= T((k-1)m,m) + m^2 + km \\ &= T((k-2)m,m) + 2m^2 + km + (k-1)m \\ &= \cdots \\ &= T(m,m) + (k-1)m^2 + km + \cdots + 2m \\ &= km^2 + km + \cdots + m \\ &= km^2 + \frac{1}{2}k(k-1)m \\ &= \Theta(km^2 + k^2m). \end{align\*} $$ Substituting $k = n/m$ and hoping for the best, we get $$ T(n,m) = \Theta(nm + n^2/m). $$ This quantity ranges from $\Theta(n^{3/2})$ to $\Theta(n^2)$.

---
Tags: time-complexity, quicksort
---


# Question
Title: How does these Probing time occurs for hash tables
I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is given here.

> Let $\alpha = N/M$ (the load factor: average number of keys per array index). Analysis is probabilistic, rather than worst-case.
>
> Expected number of probes:
>
> $$\begin{eqnarray\*} &\text{not found} & \quad\text{found}\\ \text{chaining}\quad & 1+\alpha &\quad1+\frac\alpha2\\ \text{linear probing}\quad & \frac12 + \frac1{2(1-\alpha)^2} &\quad \frac12 + \frac1{2(1-\alpha)} \\ \text{double hashing}\quad &\frac1{1-\alpha} &\quad \frac1\alpha \ln\frac1{1-\alpha} \end{eqnarray\*}$$

A clarification of why the numbers are as they are would be appreciated. :)

# Answer
> 1 votes
To give you a test of the analysis, here it is for chaining.

When the load factor is $\alpha$, the length of the list at each cell is distributed $\mathrm{Bin}(N,1/M)$, and its expected value is $N/M = \alpha$. When the probe is not found, we have to go over the entire list, and thus we have something like $\alpha$ probes in expectation. When the probe is found, the length of the list is $\mathrm{Bin}(N,1/M)$ conditioned on being positive, which is somewhat larger than $\alpha$ (and can be calculated exactly). In this case, assuming that the probed element is chosen at random from the set of all elements, its position in the list is uniformly random, and so in expectation it is found at the middle of the list, and therefore we have something like $\alpha/2$ probes.

If we are more careful then we will probably get the formulas stated at the first row of the table, or at least something very close.

The other rows of the table result from similar analysis. Each case is different. If you want to know more, I suggest you look for other online or offline resources rather than probing us here.

---
Tags: algorithm-analysis, data-structures, hash-tables, probabilistic-algorithms
---