# Question
Title: Trying to break the proof of undecidability of the halting problem
Posted this question on cstheory.SE where they said to go here:

> I read the demonstration of the Halting problem, it is done by reductio ad absurdum where the push to get to the absurd is to use the halting function "H(A,b)" (where A=another function, b=the A parameter) as its own parameter. This proofs that can't exist a function which takes every function including its own as parameter and says if it is an infinite loop or not, but doesn't proof that a function Z(A,b) where {A,b!=Z} (1\*) can't exist.

While I deleted that question I had this answer by dkuper:

> It is easy to circumvent this problem, by giving to the functions the code of a different machine which computes the same function.
>
> Say you succeeded in building your machine computing Z(a,b) which works as you said. Then you still get the reductio ad absurdum, by feeding to this machine the code of another machine which is equivalent. This is always possible because for every machine M, there are infinitely machines M′ which behaves the same as M (i.e. halt on exactly the same instances). So checking that the input is not precisely the machine M is not enough to avoid the paradox. And checking that the input does not behave the same as M is impossible.

So, now, this doesn't work if we assume that the function passed as parameter has a flag (applied by the constructor) that indicates if it is the halt function.

# Answer
> 7 votes
Let's do this step by step.

1. "Z(A,b) where {A,b!=Z}"

I understand this to mean "just forbid input Z for algorithm Z". You can not do that. A machine that is supposed to solve the halting problem has to work on *all* machines, by definition of the problem. In other words, you make the assumption "Let Z be a machine that does not solve the Halting problem" -- that does not lead anywhere.
2. dkuper's argument is correct: you can derive the contradiction by feeding *any* of the infinitely many indices of the (assumed) solver of the halting problem, arriving at the same contradiction. Since this set of indices is not recursive, you can not program your machine to detect every alias.
3. Then the machine does not solve the halting problem anymore (see 1). Even if we had some leeway there, just assume the function that solves the halting problem for all functions but the one which solves the halting problem, and do the same proof.

And when you try to fix this in the same way, I'll get another function. And another one. There are enough of them.

In other words, your strategy of fixing one (or finitely many) special cases won't lead you anywhere. The halting problem is far too undecidable for that -- as the proof shows.

---
Tags: computability, halting-problem
---


# Question
Title: How do we know that all NP problems reduce to NP-hard problems?
For example, how is it proven that any NP problem can reduce to subset sum, circuit satisfiability, etc.? Or could you link to a proof?

# Answer
Every known NP-hard problem (except a small number) was shown to be NP-hard by showing a polynomial reduction from another NP-hard problem. Obviously this wasn't true of the first problem, which was SAT. Apparently there have been a small number of problems which have been shown to be NP-hard after SAT was, but certainly the vast majority were proven by reduction to existing problems.

So how was the *first* problem shown to be NP-hard? There were two independent proofs for SAT, one by Stephen Cook in 1971 \[1\] and the other by Leonid Levin in 1973. We now know it as the Cook-Levin theorem. You can read the paper, or consult the Wikipedia article \[2\] for details, but I'll give a brief outline of the basic idea here.

Let's look at the recogniser problem. There is a language $L$, and a nondeterministic TM $M$ which recognises $L$ in polynomial time. Let $w$ be a string. The idea is to construct a boolean formula $A(w)$ in conjunctive normal form, where the number of formulas and the number of propositions is polynomial in the length of $w$ and the size of $M$ and the size of the alphabet, which is true if $M$ accepts $w$ and false if $M$ rejects $w$.

The proof depends on the fact that $M$ takes polynomial time in the length of the string. Suppose that the maximum number of steps that $M$ can take for a string of length $n$ is $Q(n)$. Then this is also an upper bound on the amount of tape that $M$ can use. We can trivially modify $M$ so that all computations take at least this time. We could, for example, modify $M$ so that it loops forever in an accepting or rejecting state, let it run for $Q(n)$ time and then see which state it was in.

We introduce the following proposition symbols:

* $P\_{i,s,t}$ is true if and only if the tape square $s$ contains symbol $i$ at time step $t$.
* $Q\_{i,t}$ is true if and only if the machine is in state $i$ at time step $t$.
* $S\_{s,t}$ is true if and only if symbol $s$ is scanned by the tape head at time step $t$.

Next, we construct formulas which model the actions of $M$ and test whether or not $w$ is accepted. We can do this using only the above proposition symbols, and in conjunctive normal form.

I encourage you to think through the details yourself by working out what the formulas might look like. The ones that Cook used are:

* At each time step $t$, one and only one square is scanned.
* At each time step $t$ and tape square $s$, there is one and only one symbol.
* At each time step $t$, $M$ is in one and only one state.
* At time step $1$, $M$ is in its start state and the tape contains exactly $w$ followed by "blank" symbols.
* At each time step transition, the $P$, $Q$ and $S$ propositions are updated correctly, according to the transition function of $M$. Remember $M$ is nondeterministic, so you need to include all possible transitions. (If you're playing along at home, use three formulas for this.)

And the final, most important, formula states that:

* $M$ enters the "accept" state at some time.

Then the conjunction of all of these formulas is true if and only if $M$ accepts $w$. Solve using your favourite SAT solver, and you're done.

---

1. The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971).
2. \[Cook-Levin theorem\] (http://en.wikipedia.org/wiki/Cook–Levin\_theorem) on Wikipedia.
> 1 votes

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


# Question
Title: Why isn't every monotonic grammar context sensitive free?
The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB---\>BA is monotonic but not context sensitive. Can someone explain to me in simple terms why this is?

# Answer
If you're asking why the grammar with the rule $AB \to BA$ is not context-sensitive, you can find an explanation here.

The short answer is that it depends on the definition, but with one standard definition, the rule $AB \to BA$ simply doesn't satisfy the criterion for a rule to be allowable in a context-sensitive grammar.
> 1 votes

# Answer
In simple terms? I'm assuming you've had enough definitions and want an intuitive understanding, so I'll orient my answer in that direction.

**Monotic grammars** are much like monotonic functions in that they *never decrease*. That is, the length of your string after the rule is applied is always greater than or equal to what it was before.

So, in the case of $AB \implies BA$, when the rule is applied, the length of the string is exactly the same; you're simply interchanging two parts. Therefore it can't decrease, therefore it is monotonic.

**Context-sensitive grammars** were introduced by Chomsky in an attempt to describe natural languages (such as English). Context-sensitive means that meaning is dependent on a term's environment. Homonyms are a great example of this:

* *"Bow towards starboard if you can see it."* Bow is an imperative verb.
* *"If you can see it towards starboard bow."* Bow is a subject noun.

An example of a context-sensitive grammar rule is $aAb \implies aBb$, because it says that you can transform an $A$ into a $B$, but only if it is between an $a$ and a $b$.

---

You might think that $$S \implies AB$$ $$AB \implies BA$$ is context-sensitive because $A$ needs to be next to $B$, but look; you can make a substitution to rewrite that grammar as: $$S \implies AB\ |\ BA$$ Which is clearly context-free. In fact, it's almost Chomsky Normal Form. As to whether that means the original is actually context-free or not, that kind of depends on your definition of context-sensitive, but it is *effectively* context-free.
> 1 votes

# Answer
When you use the classic definition, context-sensitive grammars may *inspect* the context of a non-terminal and use it to select the correct rule (cf context-free grammars), but they may *not* change it. Thus, rules like

$\qquad\displaystyle ab\mathbf{S}cD \to ab\mathbf{dca}cD$

are allowed, but like

$\qquad\displaystyle abScA \to edcBba$

are not. Note that a grammar made up of rules like this last one is monotone.

There are other definitions that characterise the same set of languages (not grammars, obviously); some are *exactly* that of monotone grammars (you have to allow $S \to \varepsilon$, though). See e.g. here.
> 1 votes

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: Local search: Problem with neighborhood definition
I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U\_k$ be the neighborhood defined as follows: $$U\_k := \\{M' : |(M' \backslash M) \cup (M \backslash M')| \leq k\\}$$

Can somebody give me an example or explain this to me?

If i choose a small k-value, the cardinality of $M'$ will be small as well, but how does an algorithm decide which matching pair of nodes to take?

If we define node-values and make it a weighted matching,let say we define a weight function $w\_e \in \mathbb{R}$ for any edge e in our graph, now the algorithm may use greedy method and take the best possible pair of nodes (with greatest weight).

But I still don't understand the exact set definition of our neighborhood.

I would be grateful for an example, because I'm stumped on this one.

# Answer
The metric used for the definition of the neighborhood is the size of the *symmetric difference*. The symmetric difference $A\triangle B$ of two sets $A,B$ is the number of elements which are in exactly one of the sets $A,B$. So $A\triangle B = (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$. A matching is considered a set of *edges*, so $M\triangle M'$ is the set of edges that are found in exactly one of the matchings. The metric is $d(M,M') = |M \triangle M'|$, and the $k$th neighborhood of a matching $M$ is the set of matchings $M'$ at distance at most $k$ from $M$.

As an example, if $M'$ results from adding an edge to $M$ or from removing an edge from $M$ then $d(M,M') = 1$, and if $M'$ results from replacing one edge of $M$ with another then $d(M,M') = 2$.
> 1 votes

---
Tags: optimization, approximation, heuristics, bipartite-matching
---


# Question
Title: Can $\emptyset$ be reducible to any other language?
While solving some question, that involved the empty set $\emptyset$, I was really wondering, is $\emptyset$ reducible to *any* other language, i.e., $\emptyset \leq A$ such that $A$ is a language over a given alphabet $\Sigma^\*$?

I mean, one can never take $x \in \emptyset$, right? or am I missing anything?

Maybe $\emptyset \leq \emptyset$? because if I take a reduction $f$ such that $x \in \emptyset \Leftrightarrow f(x) \in \emptyset$, this is always true, because $x \in \emptyset$ is never true and $f(x) \in \emptyset$ is also never true, so that function is a reduction function in the empty-concept, no?

# Answer
Recall that: a (many-one) *reduction* from $A \subseteq \Sigma^{\*}$ to $B \subseteq \Sigma^{\*}$ is a map $f : \Sigma^{\*} \to \Sigma^{\*}$ such that $x \in A \iff f(x) \in B$ for all $x \in \Sigma^{\*}$. We usually put extra conditions on $f$, such as polytime computable, but let us not dwell on that here. We write $A \leq B$ when there is such an $f$ and say that $A$ is reducible to $B$.

The statement $A \leq B$ may be written in logical notation as $$\exists f : \Sigma^{\*} \to \Sigma^{\*} . \forall x \in \Sigma^{\*} . (x \in A \Leftrightarrow f(x) \in B).$$

It is a basic exercise in logic to figure out that:

1. $\emptyset \leq B$ is equivalent to $$\exists f : \Sigma^{\*} \to \Sigma^{\*} . \forall x \in \Sigma^{\*} . f(x) \not\in B,$$ which is equivalent to $B \neq \Sigma^{\*}$.
2. $A \leq \emptyset$ is equivalent to $$\exists f : \Sigma^{\*} \to \Sigma^{\*} . \forall x \in \Sigma^{\*} . x \not\in A,$$ which is equivalent to $A = \emptyset$.

Thus, only the empty set is reducible to the empty set, while the empty set is reducible to every set, except $\Sigma^{\*}$.
> 6 votes

# Answer
$\emptyset$ can be reduced to any other language $L$ except $\Sigma^\*$.

Remember that a reduction from $L\_1$ to $L\_2$ has to map "yes" instances of $L\_1$ to "yes" instances of $L\_2$ and "no" instances of $L\_1$ to "no" instances of $L\_2$. Every input is a "no" instance of the language $\emptyset$ so, to reduce $\emptyset$ to any $L\neq \Sigma^\*$, you just need to choose some word $w\notin L$ and your reduction maps everything to $w$. Obviously, for $L=\Sigma^\*$, this doesn't work because there's no $w$ you could use.

Similarly, $\Sigma^\*$ can be reduced to any other language except $\emptyset$.
> 8 votes

---
Tags: computability, reductions
---


# Question
Title: Is there a mathematical way to deduce that my directed graph is disconnected?
I have a graph G with 13814 nodes and 25190 edges. I am interested in finding a mathematical proposition that proves that my graph is disconnected. I know it is, because the visualization shows lonely clusters where they have no way of reaching the other nodes in the graph. This simply is a signature of disconnected graphs. But, is there a mathematical way to prove whether my graph is disconnected?

# Answer
You can choose any random node and touch any all the nodes linked to that node and all the children (BFS, DFS or any algorithm like minimum spanning tree). After that, you can check if there are untouched nodes, and if there are, then it implies that your graph is disconnected.
> 5 votes

# Answer
If the multiplicity of zero as an eigenvalue of the Laplacian of your graph is greater than one, your graph is disconnected.
> 3 votes

# Answer
There is one way to derive disconnectivity from number of nodes $n$ and edges $m$ alone: if $m \< n-1$, the graph is disconnected.

That is not the case for your graph. There may be other parameters/properties that allow the conclusions, but it's unlikely you can compute these faster than the naive approach (if you don't have them given in your setting):

Perform a graph traversal starting in any node. If it does not visit all nodes, your graph is disconnected.
> 3 votes

---
Tags: graphs
---


# Question
Title: Turing machine which diverges on its own code
> Show that the set $K^{c}$ = $\lbrace M \mid M(M) \text{ diverges} \rbrace$ is not recursively enumerable.

This question is essentially asking to show that the set of turing machines which diverge when run on their own code is not RE.

My idea is to attempt to reduce this problem to something which is the complement of the halting problem. Thus, the idea is to take a machine M and a word w, and construct a new machine which diverges on it's own code when M diverges on w, but haven't had much luck with that.

This is from a practise exam, but please treat it as a homework question so I can attempt to work through a solution.

# Answer
> 4 votes
The language $K^c$ is clearly co-RE: given an input $M$, simulate $M(M)$ until it halts and then reject; if it doesn't halt, the simulation doesn't halt. Now, any language that is both recursively enumerable and co-RE is actually recursive (exercise: prove this). Since $K^c$ is not recursive (exercise: prove this), it cannot be recursively enumerable, either.

Your idea of reducing to the complement of the halting problem doesn't work. Firstly, that's the wrong way around: you'd want to reduce the complement of the halting problem to $K^c$ to prove that $K^c$ is hard. Second, it's possible for a set to be neither RE nor co-RE. (Why? There are countably many RE languages and countably many co-RE languages, since each such set corresponds to a Turing machine and there are only countably many Turing machines. But there are uncountably many languages over any finite alphabet.) However, from your description, it sounds like you weren't trying to do a reduction but a diagonalization, similar to the proof of the undecidability of the halting problem. That sounds like it could work but the method I give above is much easier.

# Answer
> 0 votes
One way I can think to prove this is to consider a turing machine $N$ deciding $K^c$, and construct another tm $M$ such that in the input $\left \< R \right \>$ runs $N(\left \< R\right \>)$ and does the opposite of what $N$ responds. You should be able to get a contradiction when $M$ runs on its own input.

Another way would be to, given a input $\left \< M,w \right \>$ for the halting problem, construct a tm that ignores its input and runs $M(w)$. This tm behaves the same way independtly of its input, so in particular it halts in its own code iff $M$ halts on $w$.

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


# Question
Title: Can a semi-decidable problem be also decidable?
As far as I understand, a `semi-decidable (recursively enumerable)` problem could be:

> 1. decidable (recursive) or
> 2. undecidable (nonrecursively enumerable)

This post made me wonder if this is not conventionally followed. This is my answer to it and as far as I understand it is correct:

> A semidecidable problem (or equivalently a recursively enumerable problem) could be:
>
> *Decidable*: If the problem and its complement are both semidecidable (or recursively enumerable), then the problem is decidable (recursive).
>
> *Undecidable*: If the problem is semidecidable and its complement is not semidecidable (that is, is not recursively enumerable).
>
> *Important note*: Remember that a decidable (recursive) problem is also semidecidable (recursively enumerable). Conversely, if a problem is not recursively enumerable (semidecidable), then is not recursive (decidable).

What the Wikipedia entry says is that:

> Partially decidable problems that are not decidable are called undecidable.
>
> In general, a semidecidable problem (recursively enumerable) could be decidable (recursive) or undecidable (nonrecursively enumerable).
>
> Also note that a problem and its complement could both (or just one of them) be not even semi-decidable (nonrecursively enumerable). Also note that, if a problem is recursive, its complement is also recursive.

Is it conventionally (always) understood this way? Is there some literature that presents semi-decidability (partially decidable, recursively enumerable) problem as an equivalent of undecidability?

# Answer
> 9 votes
Yes, a recursively enumerable language may be either decidable or undecidable. To see this, you ust look at the definitions of the terms.

A language $L$ is recursive (aka decidable) if there is a Turing machine that halts for all inputs, accepting every word in $L$ and rejecting every word not in $L$. $L$ is recursively enumerable (aka semi-decidable) if there is a Turing machine that halts and accepts any input in $L$ and, for any input not in $L$, it either halts and rejects or it does not halt.

Therefore, every recursive language is recursively enumerable. The machine that decides the recursive language is a special case of the machine required for a recursively enumerable language: specifically, it is allowed to either loop forever or reject for words not in $L$; in fact, it always rejects and never uses the option of looping forever.

---
Tags: terminology, computability, undecidability, semi-decidability
---


# Question
Title: Minimum number that cannot be formed by any subset of an array
We have an array of Integers, $A\[\]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP approach, and outputing the min number with value infinity. But the problem is that the sum of ranges can be as large as 109, and we have about 105 queries of the type $\[L,R\]$, so I was hoping there'd be a better approach. Can anyone point me in the right direction?

There are 105 elements in the array

Suppose the elements of the array are 1,1,2,7. Then for indices 1 and 4, the smallest number that cannot be formed as a sum is 5. since we can form all 1,2,3,4.

# Answer
You can pre compute an array $B$ such that $B\[0\]=0$ and $B\[i\]=B\[i-1\]+A\[i-1\]$. That you can use $A\[L,R\]=B\[R+1\]-B\[L\]$ to speed up you computations.

Now you can enumerate all pairs $A\[L,R\]$ and insert them into some sorted data structure $T$, and then you will be able to enumerate all of them in a sorted fashion, and thus answer your question.

This will still be in complexity $O(n^2\log n)$ where $n$ is the size of $A$ but it will not change even if the numbers in $A$ are large. This is not fundamentally faster than proposed solution, I don't know if there is indeed a faster one.
> 0 votes

---
Tags: data-structures, dynamic-programming
---


# Question
Title: Check if there exist A and B such that S=A+B and T=B+A
Two strings $S$ and $T$ are said to be *conjugate* if there are two non-empty strings $A$ and $B$ such that $S = A+B$ and $T = B+A$ ($+$ is concatenation). How can I find if two strings are conjugate or not?

Example: if `S="tokyo"` and `T="kyoto"`, then the pair $(S,T)$ is conjugate, because we can find `A="to"` and `B="kyo"`.

# Answer
If $S = A + B$, then $A$ is a prefix of $S$ and $B$ is a suffix of $S$. So you only need to try the strings $A$ which are a prefix of $S$ and the strings $B$ which are a suffix of $S$.

Furthermore, given a string $A$, not all suffixes of $S$ can work: only the one $B$ such that $A + B = S$.

So go through the prefixes of $A$, and test them against $T$.

Note: there are more sophisticated algorithms that can run faster. But at this level, what you're expected to write is an algorithm that makes a single pass over all the prefixes of $S$, and for each prefix, determines whether it is part of a solution in time $O(n)$ where $n$ is the length of the strings $S$ and $T$.
> 2 votes

---
Tags: algorithms, strings
---


# Question
Title: What is the field studying the search and generation of computer programs?
This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that integer sequence. I was trying to approach the same idea using lambda-calculus instead of a stack-based language, but I was stuck on the enumeration of valid programs on LC's grammar.

Anyway, what is the field studying that kind of idea and how can I grasp the current state-of-art?

# Answer
> 3 votes
What you are describing is a *Kolmogorov complexity* approach. The Kolmogorov complexity of an integer sequence (or a string) is the size of the minimal program computing it (in some fixed Turing-complete language). Here we're looking for the minimal program which generates $n+1$ numbers, the first $n$ of which are the given sequence.

Kolmogorov complexity is not computable - that is, one cannot compute the size of a minimal program computing a given sequence. The implementation you mention computes a restricted version of Kolmogorov complexity in which the programs are very simple (and always halt).

Another (non-computable) approach is the *universal probability distribution* in which a given integer sequence of complexity $x$ is given a probability in proportion to $2^{-x}$. By conditioning on the first $n$ numbers produced, we can construct a probability distribution on the next number. By restricting the set of programs, we can make this distribution computable (though perhaps not efficiently).

# Answer
> 3 votes
This is broad, studied and impinging in several different areas, and not confined to the following:

* Program synthesis. The idea is that a formal specification of the program's input & output relationship is given and software can be used to search or derive for programs that satisfy the specification. Here are some recent research results at Microsoft.
* Genetic programming and genetic algorithms. This is a field in machine learning where evolutionary processes are used to evolve functioning programs.

---
Tags: algorithms, complexity-theory, formal-languages, computability, regular-languages
---


# Question
Title: Is any language that can express its own compiler Turing-complete?
A comment over on tex.SE made me wonder. The statement is essentially:

> If I can write a compiler for language X in language X, then X is Turing-complete.

In computability and formal languages terms, this is:

> If $M$ decides $L \subseteq L\_{\mathrm{TM}}$ and $\langle M \rangle \in L$, then $F\_L = \mathrm{RE}$.

Here $L\_{\mathrm{TM}}$ denotes the language of all Turing machine encodings and $F\_L$ denotes the set of functions computed by machines in $L$.

Is this true?

# Answer
The informal statement is not true, as shown by the following programming language. Any string of, say, ASCII characters is a valid program and the meaning of every program is, "Output a program that just outputs a copy of its input." Thus, every program in this language is a compiler for the language but the language is not Turing-complete.

I'm not sure if your "computability theory version" is equivalent but it is also not true. By Kleene's second recursion theorem, for any coding of Turing machines, there is a TM that accepts its own coding and rejects all others.1 This machine is a counterexample to the proposition. More concretely, we can achieve the result by choosing a coding. For example, let every odd number code the machine $M$ defined by "If my input is odd, accept it; otherwise, reject" and let the number $2x$ code the machine coded by $x$ in your own favourite coding scheme for Turing machines. $\langle M\rangle$ is in the language $L$ accepted by $M$ but $F\_L$ is not Turing complete.

---

1 Kleene's second recursion theorem says that, for any enumeration $(\phi\_i)\_{i\geq 0}$ of the partial recursive functions (i.e., for any coding of programs as integers), and any partial recursive function $Q(x,y)$, there is an integer $p$ such that $\phi\_p$ is the function that maps $y$ to $Q(p,y)$. So, in particular, let $Q$ be the function that accepts if $x=y$ and rejects otherwise. By the theorem, there is an integer $p$ that codes the program $\phi\_p(y) = Q(p,y)$. That is, $\phi\_p$ accepts its own coding $p$ and rejects all other inputs.
> 14 votes

---
Tags: computability, turing-completeness
---


# Question
Title: Which algorithms can not be parallelized?
Is there any algorithm which is very difficult to parallelize or the research is still active?

I wanted to know about any algorithm or any research field in parallel computing.

Anything, I searched for, has a 'parallel' implementation done. Just want to do some study on any unexplored parallel computing field.

# Answer
> 13 votes
this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms.

in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $n$-body problems maybe relatively difficult to efficiently parallelize as the $n$ increases because there are $n^2$ interactions between all the $n$ points.

they added 6 others later in the paper and suggest that a last one called "FSMs" (p14) where the problem involves computing FSM like calculations (such as the $n$th state of the FSM) may be the opposite of "embarrassingly parallel" something they propose calling "embarrassingly sequential".

see also are there famous algorithms in sci. comp. that cant be parallelized, scicomp.se

# Answer
> 13 votes
This article gives a number of problems that are easy to solve sequentially but difficult to parallelise: http://en.wikipedia.org/wiki/P-complete

The **circuit value problem** ("given a Boolean circuit + its input, tell what it outputs") is a good starting point — easy to understand, easy to solve with sequential algorithms, and nobody knows if it can be parallelised efficiently.

# Answer
> 9 votes
From a practical-oriented perspective, you are asking about inherently-sequential algorithms. There are many candidates, such as hash-chaining, which is believed to be very difficult to parallelize. Hash-chaining is widely used in cryptography. For instance, the password-hashing scheme bcrypt was designed to try to make it difficult to speed up the hash through parallelization. Another example is repeated-squaring (again, in cryptography).

---
Tags: algorithms, parallel-computing
---


# Question
Title: What is an estimation of the Kolmogorov Complexity for the first N integers?
I'm aware some ints have higher or lower Kolmogorov Complexities. For example, the number `5.41126806512` has a very low complexity as it can be expressed by `17/pi`. I'm also aware that, though the KC varies depending on the expression language, it is always the same up to a given constant. So, I ask: is there a way to calculate an **approximation** of the KC for the first N ints?

# Answer
No, there is no general algorithm to compute a close approximation to the Kolmogorov complexity of the sequence $1,2,\dots,n$. Any candidate algorithm you come up with will have some inputs where it gives a bad answer (a poor approximation to the correct answer).

Denote by $\[n\]$ the binary encoding of the natural number $n$, and let $\[\[n\]\] = \[1\],\[2\],\ldots,\[n\]$ denote a comma-separated encoding of the sequence $1,\ldots,n$. It is not hard to check that $|K(\[n\]) - K(\[\[n\]\])| = O(1)$. Since computing $K(\[n\])$ is undecidable, it follows that computing a good approximation to $K(\[\[n\]\])$ is also undecidable.

Furthermore, it is known that for "most" integers $n$, $K(\[n\]) = \Theta(\log n)$. So for "most" integers $n$, $K(\[\[n\]\]) = \Theta(\log n)$.
> 6 votes

# Answer
One way of expressing the statement 'almost all numbers are maximally random' is as the assertion that $\sum\_{i=1}^N K(i) \in\Theta(N\lg N)$. For convenience's sake, set $N=2^k$ and consider just the portion of the sum from $2^{k-1}$ to $2^k$; then for each $c$ we have that the number of numbers of this length with complexity $\geq k-c$ is $2^{k-1}-2^{k-c}$ (see http://en.wikipedia.org/wiki/Kolmogorov\_complexity for some details of this), so we can split the sum into the sum of the '$c$-incompressible' numbers and the compressible numbers, with the former contributing at least $(1-2^{1-c})2^{k-1}(k-c)$ to the sum. A bit more massage should be enough to get you a constant of the form $1-o(1)$ in front (i.e., a sum of $N\lg N-o(N\lg N)$).
> 2 votes

---
Tags: complexity-theory, kolmogorov-complexity
---


# Question
Title: How close are common programming languages to not being Turing complete?
The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually requires. I found this question, but the answers are a bit more mathematical than what I am looking for.

Take a common programming language, such as C++, Python, Java or Lisp. How close are these languages to being not Turing complete? Do these languages have elementary features that if removed would make the language not Turing complete? Or could you change a property of the language (for example, making something random) and by doing that make the language not Turing complete?

# Answer
> 8 votes
Common programming languages are very firmly Turing-complete, if you take an idealized view where programs can use an arbitrary large amount of memory. There typically isn't a single feature that you can isolate without which the language wouldn't be Turing-complete.

Intuitively speaking, Turing completeness requires two things:

* A way for programs to manipulate an amount of memory that doesn't solely depend on the size of the input. Any form of object creation that can build bigger objects from smaller objects is suitable: objects, structures, pairs, lists, `malloc`, `new`, etc. Even stack-based allocation is enough provided that there is a way to access objects at any distance from the top of the stack (with only stack-based allocation and only access to the top of the stack, you only get a pushdown automaton). Many weaker forms of data manipulation are also suitable: for example, in a language like Lisp or Python where integers don't have a limited size, the basic integer operations alone are enough for Turing completeness.
* A way for programs to keep running or halt based on some part of the data. While loops, recursion plus some form of conditional (e.g. `if` or `case`/`switch`) and `goto` plus some form of conditional are the three common ways, but there are others.

I think that the best way to understand what makes a language Turing-complete is to look at examples of languages that are powerful, but not Turing-complete. I'll give two examples that illustrate the two main families of such languages (other than languages that operate in bounded memory).

Consider an imperative language with integer operations and arrays, but only for loops (`for i = 1 to n`, where `i` cannot be modified during the loop), not arbitrary (while) loops and no recursion. BlooP and early versions of FORTRAN are examples. In such a language, you can only express primitive recursive functions — functions where the amount of computation is bounded in the size of the input. The language is not Turing-complete — cannot express arbitrary recursive functions — because of the bound on computation time.

A functional language can be made non-Turing-complete by restricting recursion through a type system that restricts all functions to be terminating. If the type system is decidable (i.e. if it is decidable whether the program is well-typed), then such a language cannot be Turing-complete (because the halting problem is undecidable). Languages used for theorem proving, such as Coq and Agda, are of this kind.

See also What can Idris not do by giving up Turing completeness?

---

On a side note, theorem provers require the user to input termination proofs (i.e. they don't find them themselves). So you could make a theorem prover with an undecidable type system: if you get a correct proof accepted, you're happy, otherwise you give up after a while. But it wouldn't be user-friendly. Most theorem provers have a decidable type system: you enter a term, and either it's accepted or you get a type error back. What theorem provers don't have is decidable type *inference*: if you type a term with partial type information and it's rejected, you don't know whether it's because the term cannot be typed or because the inference engine wasn't smart enough.

---
Tags: programming-languages, turing-completeness
---


# Question
Title: What program will derive the underlying algorithm in these question-answer pairs (updated)?
Given this set of question-answer pairs, what program will derive the underlying algorithm and provide the correct answer for any question of the same format.

**Question-Answer Pairs (training set):**

```
B:BA
BA:BB
BB:BAA
BAA:BAB
BAB:BBA
BBA:BBB
BBB:BAAA
BAAA:BAAB
BAAB:BABA

```

Those familiar with binary may notice that the training set is binary numbers with A and B substituted for 0 and 1. The answer to each question is the next binary number (using A and B).

After processing the training set, the program should be able to answer questions such as the following using the algorithm it derived:

```
BABA:?
BABB:?
BBBBAAA:?
BAABBAAABBABA:?

```

**Constraints:**

* The program must derive the counting algorithm **only by manipulating the data given** in the training set. It must not use hard coded knowledge of binary counting.
* Many algorithms may produce the correct answers. Therefore, **the simplest algorithm is preferred**.
* The program should assume that **each answer is a transformation of the question**.
* All questions will be in the binary format seen above, but they may be of arbitrary size.

Can any existing machine learning programs/algorithms solve this? If so, how? If you believe this is unsolvable, please explain why.

---

*This update contains background to the question, explanation of the problem space, a new constraint, a proposed solution, and further questions.*

This problem is relevant to general machine learning where the machine must learn by observation and feedback the algorithms that govern the world around it.

Based on Kolmogorov complexity, there is at least one program that can produce the correct mappings:

```
if B, then BA
if BA, then BB
(etc. for all pairs in training set)

```

This will work for every pair in the training set and nothing else. This will be the shortest program if the training set is completely random. The good news is that this is an upper bound. For any training set that is not random, there will be a smaller program that will work. Also, the number of programs smaller than upper bound is finite.

A unfortunate result of Kolmogorov complexity is that it cannot be calculated. This is due to the halting problem. We can't know if any program will stop until it does.

If the question is "Write pi," then the program that produces the correct answer would never halt because pi has infinite digits. An answer infinitely long is never desirable so I think the best way to deal with this is to put an **arbitrary limit on the length of the answer**.

With that additional constraint, here is an (inefficient) program that will generate a correct solution program shorter than the upper bound if one exists. (sorry of this is confusing, but these steps outline a program that generates programs that implement an algorithm to map questions to answers in a training set):

1. Create the "upper bound" program. One that maps each input in the training set directly to its output.
2. Generate every possible program that is shorter than the upper bound and list them from shortest to longest.
3. Starting with the shortest program, run the first step of every program.
4. Stop when a correct program is found.
5. Eliminate programs that stop without a correct answer or produce an answer longer than the arbitrary limit.
6. Repeat steps 3-5 running the second step, third step, etc. of the programs.

This program has the following benefits:

* It limits the number of programs to those smaller than the "upper bound" program.
* It avoids the halting problem by
    + incorporating an arbitrary limit to the length of the answer and
    + executing step x in all programs before moving on to step x+1 so that the solution will be found before looping infinity.

The main disadvantage is that it is terribly slow. It takes millions of years to crack a 128 bit password and I think this program could have comparable performance.

**Now, the questions:**

* Do you see any significant flaws in this solution?
* Can this program's performance be improved in any significant way without introducing onerous constraints?

# Answer
> 1 votes
The same answers you got the last time you asked this question apply. There are infinitely many possible mappings $\\{A,B\\}^\* \to \\{A,B\\}^\*$ and none is preferable to any other.

Let's try to formalize your problem more clearly. I suspect you want an algorithm to solve the following problem:

> Given a training set as input (i.e., a set of mappings $x \mapsto y$, where $x,y$ are strings), output the shortest algorithm $A$ with the property that $A(x)=y$ for every $x,y$ in the training set.

The bad news is that this problem is not solvable. In particular, the problem is undecidable, so you should not expect any general algorithm to solve this problem. To do better, you will need some structure on the set of hypotheses (e.g., a distribution on possible mappings or something like that).

Why is this undecidable? Because it is basically the problem of computing the Kolmogorov complexity of the training set, and computing the Kolmogorov complexity is known to be undecidable.

You might be wondering how standard methods for machine learning get around this barrier. The answer is that they avoid this barrier by changing the problem statement. Machine learning methods generally involve a more restricted space of hypotheses (instead of allowing all possible algorithms, we only consider a restricted subset, such as those that are linear or that have some other nice properties) or else involve specifying a probability distribution on the set of possible mappings. I recommend you spend some time studying machine learning.

---

What is the context and motivation for your question? What's the *specific* real-world situation where you encountered this? To make progress I suspect you'll need to step back and look at the real requirements from your application, and be open to other ways to meet your needs.

---
Tags: machine-learning, artificial-intelligence
---


title: Number of K-sets

text:
# Question
Title: Number of K-sets
I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}.

I need to to know how many K-sets exist(here K-set refers to set of points whose distance between 2 points of set is K).But as there can be infinite number of these K-sets. Thus, we would only like to count the number of classes of K-sets, such that any two K-sets which belong to the same class are equivalent if they follow given conditions.Two K-sets X and Y are considered equivalent (and belong to the same class) if:

```
They contain the same number of points
There exists N integer numbers (t1, ..., tN) such that by translating each point of X
 by the amount ti in dimension i (1≤i≤N) we obtain the set of points Y.

```

Let's consider N=2, K=4 and the following sets of points X={(1,2), (5,5), (4,3)} and Y={(2,5), (5,6), (6,8)}. Let's consider now the tuple (1,3). By translating each point of X by the amounts specified by this tuple we obtain the set {(2,5), (6,8), (5,6)}, which is exactly the set Y. Thus, the two sets X and Y are equivalent and belong to the same class.

Example let say N=2 and K=1 .

There are 9 classes of K-sets. One K-set from each class is given below:

```
{(0,0), (0,1)}
{(0,0), (1,0)}
{(0,0), (1,1)}
{(0,1), (1,0)}
{(0,0), (0,1), (1,0)}
{(0,0), (0,1), (1,1)}
{(0,0), (1,0), (1,1)}
{(0,1), (1,0), (1,1)}
{(0,0), (0,1), (1,0), (1,1)}

```

So answer here will be 9.

# Answer
I'm going to assume that the problem is to devise an algorithm to count the number of equivalence classes of $K$-sets on $\mathbb{Z}^N$, given $K,N$ as input.

To help us count them, let's pick a canonical representative for each equivalence class. One way to do that is to pick the $K$-set that contains the point $(0,0)$: the equivalence class must contain exactly one such set, so it can be used as the canonical representative.

So now the problem becomes:

> Given $K,N$, count the number of sets of points from $\mathbb{Z}^N$ that contain the point $(0,0)$ and such that every pair of points in the set is at distance exactly $K$ from each other (using the $L\_\infty$ distance).

Computing this is pretty straightforward. Suppose that $S\_1,\dots,S\_m$ is the list of all such sets of size $s$. For each $S\_i$ and each $x \in S\_i$, there are $N$ possible points $y$ that are at distance $K$ from $x$; enumerate them all. Then, for each such $S\_i,x,y$, test whether $y$ is at distance $K$ from all other points of $S\_i$ and whether $y\notin S\_i$; if both conditions hold, then $S\_i\cup \\{y\\}$ is a valid set of size $s+1$. Continue in this fashion, enumerating first all sets of size $1$, then all sets of size $2$, then all sets of size $3$, etc., until no more can be found.

The running time of this algorithm will be at most $O(nNs)$, where $n$ is the total number of such sets (equivalence classes), and $s$ is the maximum size of any such set.
> 1 votes

---
Tags: algorithms, computational-geometry, sets, number-theory
---


# Question
Title: Using interval graphs to find authorship disputes
The first chapter of the book "Graphs and their uses" by Oystein Ore says that interval graphs can be used to resolve authorship disputes, but I couldn't find any details. How does this work? What is the algorithm?

**From the text (Chapter 1.7):**

> Interval graphs have also been used to investigate the likely authorship of disputed pieces of writing, such as certain works of Plato. Various features of an authors prose style are studied for their appearance in several literary works. By drawing a graph in which the vertices correspond to these literary features and the edges correspond to pairs of them which occur together in the same work, we obtain a situation very similar to our archaeological example. As before, we can then investigate whether the resulting graph can be represented as an interval graph, and we can thereby attempt to arrange the works in chronological order. By doing this, it has sometimes been possible to relate the style of the disputed piece of writing to that of the author in question, and thereby to determine the likely authorship.

# Answer
> 1 votes
I'll explain shortly the "archaeology example" your excerpt refers to. It seems that the authorship dispute problem is really no different from it, and any practical application would face similar problems as I will describe.

Around 1900, Flinders Petrie formulated a problem known as *sequence dating* while studying 800 types of pottery found in 900 Egyptian graves. To each artifact, we associate a time interval (unknown) during which it was used, and to each grave a time point (unknown) when its contents were interred. Then, the problem is to figure out the time relationships between the artifacts and the graves.

Now consider a graph $G$ whose vertices correspond to distinct artifacts. There is an edge between two vertices if they were found in some common grave. Assuming each pair of artifacts whose usage intervals intersect are to be found together in some grave we have that $G$ is an interval graph. Furthermore, an interval assignment for $G$ is a candidate for the usage intervals of the artifacts. However, of course in practice, it might be that we have incomplete data so the assumptions do not hold, and in any case, we need additional techniques to choose the correct interval assignment.

---
Tags: graphs, natural-language-processing
---


# Question
Title: What's the difference between "polynomial time Turing-reducible" and "polynomial time many-to-one reducible"?
The following definitions are from Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38.

> A language $A$ is called *polynomial time Turing-reducible* to a language $B$, denoted as $A\leq\_T^P B$, if given $B$ as an *oracle*, there is a deterministic Turing machine that accepts $A$ in polynomial time. That is, we can accept $A$ in polynomial time given answers to membership of $B$ for free.
>
> A language $A$ is called *polynomial time many-to-one reducible* to a language $B$, denoted as $A\leq\_m^P B$, if there is a function $r$ that is a polynomial time computable, and for every $a$, $a\in A$ iff $r(a)\in B$. In both cases, if $B\in P$, then so is $A$.

Aren't the two definitions equivalent? What's the difference?

# Answer
> 1 votes
A polynomial-time many-one reduction is a polynomial Turing reduction that only calls the oracle once, and that returns the oracle's answer without any further computation.

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


# Question
Title: Is it possible to design a C++ like language without a Preprocessor?
According to the dragon book, one of the first steps the source code of a program goes through during compilation is the Preprocessor.

Assuming a language like C++ where there is no underlying virtual machine to abstract away the underlying platform, is there a way to deal with cross platform compilation without requiring the use of the Preprocessor?

Another use case would be code to remove code that should only be executed in "Debug Builds".

P.S: I'm not mentioning other uses of the preprocessor like defining a value for PI as these can easily be replaced with the use const global variables.

# Answer
Yes, it's entirely possible.

For example, you can define the language as requiring at least a minimal degree of dead-code elimination, so (for example) something like:

```
const bool debug = false;

if (debug)
    whatever();

```

...*requires* that not only is `whatever()` not *called*, but that it produce code that does not refer to `whatever` at all.

This gives roughly the same effect as something like:

```
#if debug
    whatever();
#endif

```

...would in C or C++. The only obvious difference is that by including the capability in the language, you typically require that the contents of the condition be syntactically correct for the target programming language (whereas C and C++ allow an `#ifdef` block to contain code that isn't syntactically correct C or C++, as long as the preprocessor can still detect the matching `#endif`).

Now, in some cases it's easy to require things that nobody knows how to do, thus producing a specification that nobody can implement. That would not be the case here though: compilers that can do the optimization above already exist.

Ada, for one example, includes a great deal of ability to tailor code to a specific platform without using a preprocessor like C and C++ do. In fact, it (Ada) arguably supports quite a bit more than C and C++ do in this regard.
> 6 votes

---
Tags: programming-languages
---


title: Type checking on assignment

text:
# Question
Title: Type checking on assignment
I want to develop an interpreter. In the language, you have values and variables and types. The literals (the values) belong to some basic type. The subtypes can constrain the range of values. The spec says that making assignment, we ensure that the value assigned is assignable to the target (variable) range. Is it worth do the check on every assignment or ensure statically? How do you ensure it statically?

In the current implementation, I see that a type is attached to every value object. Are there are better approaches?

# Answer
It depends on how the language is defined.

Language might be statically typed (like e.g. C, Java, Haskell, ...) or dynamically typed (like e.g. Python, Common Lisp, ...). In a statically typed language every expression has associated value and the semantic analyser checks whether the types match just after when the expressions are parsed.

In a statically typed language if you have variable `a` defined to contain integer and variable `b` defined to contain integer between 0 and 10, assignment `b = a` is not valid at compile. Of course such language needs a way of saying "please check whether the value will fit and set it if it does and do that if it does not". Usually via some kind of type cast that throws an exception, but might be anything.

In a dynamically typed language expressions don't have any type specified and whether the value can be assigned is always checked at runtime when specific type is needed.

Combination is possible where expressions *may* have associated type and if they don't, they are considered to be of universal "any" type and runtime check is omitted if it is possible to statically ensure the value will fit.

Then there are strongly typed languages (e.g. Java, Python, Haskell, ...) and weakly typed languages (C, C++, Pascal). In a strongly typed language each value has associated type and this type may be checked at runtime if needed. On the other hand in weakly typed languages the value is just a bit pattern and gets interpreted according to the static type of the expression. Note that dynamically typed languages are strongly typed as their values carry their type around with them.

Since your language has variable types, it is at least partially statically typed. So you can do some static type checking. If you have assignment of variable that can hold positive numbers to variable that can only hold negative numbers, you can reject such statement straight away without waiting for the actual values, because the ranges are disjoint (the types are incompatible).

If the type on the right hand is a subtype of the one on left hand (the range is smaller), you know the statement will always be ok. You don't need to do a check at runtime.

If the types have some overlap, but the type on right hand is not a subtype, i.e. may have values that don't fit in the variable on the left side, you may either require explicit check or you may automatically inject a check that will yield error or exception if at runtime the actual value does not fit. Which you do depends on the specification of the language.

Last for constants you handle them as special case of the subtype rule. A constant 42 is an integer in range \[42, 42\]. This is a subtype of all ranges that can contain 42 and you can do the check at compile-time.
> 3 votes

---
Tags: type-checking, interpreters
---


# Question
Title: Solving the recurrency $T(n) = 2T(\sqrt{n}) + O(1)$
I need to solve the following recurrency: $T(n) = 2T(\sqrt{n}) + O(1)$. It's for a simple undergrad problem that a student asked me, but I really couldn't solve it. Since it is for an undergrad question, it would be nice to solve it only with algebraic manipulation and reduction to a well known recurrence, or in the end use the master theorem or a recursion tree. Looking at this question, I tried to make $m=\log(n)$, but I got lost at squeezing the $\log$ inside the term $T(\sqrt{n})$. Is it like $T(\log(\sqrt{n}))$ or $T(\sqrt{\log(n)})$? Or is this the wrong approach?

# Answer
Since Master theorem is in terms of fractions of $n$ in the recurrence, and you have a fractional **power** of $n$ in the recurrence, try to convert between powers and multiplications. Taking $\log$ or $\exp$ of something usually helps with that.

Let $x=\log n$, $F(x)=T(\exp x)$. Then you have this recurrence:

$F(x)=T(\exp(\log n))=T(n)=2T(\sqrt n)+O(1)=2T(\exp (\frac{1}{2}\log(n)))+O(1)=2F(\frac{x}{2})+O(1)$

Then apply Master theorem to $F(x)$ and get $F(x)=O(x)$.

Therefore $T(n)=F(\log n)=O(\log n)$.
> 3 votes

# Answer
You can do without the Mastertheorem, by simply counting the number of nodes, since the overhead is constant. Let's assume $\forall n \leq 2: T(n) = 0$, then the height $k$ of the tree is bound by \begin{align\*} n^{\frac{1}{2^k}} &\geq 2 \\ \Rightarrow n^{\frac{2^k}{2^k}} &\geq 2^{2^k} \\ \Rightarrow k &\leq \log\_2\log\_2 n \mbox{ .} \end{align\*} So $T(n) \leq c\[2^{k+1}-1\] \leq 2c\log\_2 n - c \in O(\log n)$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Smallest DFA that accepts given strings and rejects other given strings
Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^\*\setminus B$?

In other words, $A$ represents a set of positive examples. Every string in $A$ needs to be accepted by the DFA. $B$ represents a set of negative examples. No string in $B$ should be accepted by the DFA.

Is there a way to solve this, perhaps using DFA minimization techniques? I could imagine creating a DFA-like automaton that has three kinds of states: accept states, reject states, and "don't-care" states (any input that ends in a "don't-care" state can be either accepted or rejected). But can we then find a way to minimize this to an ordinary DFA?

You could think of this as the problem of learning a DFA, given positive and negative examples.

This is inspired by Is regex golf NP-Complete?, which asks a similar questions for regexps instead of DFAs.

# Answer
A DFA as you describe is called a *separating DFA*. There is some literature on this problem when $A$ and $B$ are regular languages, such as Learning Minimal Separating DFA’s for Compositional Verification, by Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang

Note that as @reinierpost states, without any restrictions on A and B, the problem may become undecidable.
> 7 votes

# Answer
There is a lot of literature on learning DFAs given positive and negative samples. If $A$ and $B$ are finite I don't see how the problem would ever be undecidable though. If $A \cap B = \emptyset$ then obviously the DFA that accepts only the strings in $A$ satisfies your requirement and one can simply enumerate all smaller DFAs. If $A \cap B \neq \emptyset$ then clearly no such DFA exists.

Finding the minimum DFA consistent with a given set of strings is NP-complete. This result appears as Theorem 1 in Angluin's paper On the complexity of minimum inference of regular sets. So clearly your problem is also NP-complete.

For lots of good links and discussion on learning regular languages check out the CSTheory blogpost On Learning Regular Languages.
> 8 votes

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


# Question
Title: Trying to tag parts of a word and keep track of any changes that happen to those parts
I'm a researcher working with a language that has gone through phonological changes through time. I would like to tag parts of a word (i.e. prefix, stem, suffix) and then apply those phonological changes and then see what is left or different about the stuff that I tagged.

I'm currently using Python with some regex stuff to apply the changes so if I can do this using its NPL toolkit that would be perfect. I've start to mess around with it but I haven't found anything that will work just yet. I'm also not sure if this toolkit would be the best for this.

For example, I apply the following transformation to tag `re`, `peat` and `ed` in `repeated`: $$ \begin{align} \mathtt{repeated} & \xrightarrow{\mathtt{rep} \mapsto \mathtt{rp}} \mathtt{rpeated} \\ & \xrightarrow{\mathtt{ea} \mapsto \mathtt{e}} \mathtt{rpeted} \\ & \xrightarrow{\mathtt{d}\\$ \mapsto \epsilon} \mathtt{rpete} \\ \end{align} $$

I would like to be able to find out what is left of the stuff I tagged. So I'd like to see that `r` is all that is left of the prefix, `pe` is all that is left of the stem, etc. Any help or direction is greatly appreciated!

# Answer
> 1 votes
You can use sequence alignments with a suitable score. You then get something like this:

$\qquad\displaystyle \begin{array}{cccccc} r & e & p & e & a & t & e & d \\ r & - & p & e & - & t & e & - \end{array}$

Now, if you have marked the original word, you can read off that -- according to your alignment score -- only "r" is left from the prefix, "pet" from the stem and "e" from the suffix.

The score makes a difference when parts may be assigned to e.g. prefix or stem. Levenstein/edit distance and Damerau-Levenstein distance may be good starting points. Play around with the penalties a bit; note that you can assign costs depending on whether you match against prefix, stem or suffix (if you have marked the original words) and use things like affine gap costs.

---
Tags: algorithms, strings, natural-language-processing, computational-linguistics
---


# Question
Title: How to evaluate recommendation engine without ground truth?
I have developed an algorithm which recommends geographical locations to users based on popular trends and their own interests. The dataset is created by my organization. So the user selects a few categories and based on his interest and rating by other people he is presented with recommended places for him.

How do you evaluate or use metrics for such system given that ground truth doesn't makes sense in this case ?

**EDIT:** I meant that how to evaluate the accuracy or quality of results in such case especially for published work.

**EDIT 2** (as per the request for details in the comments)

Details of the system

1. The user indicates his preferences from a predefined set of tags (cultural, mountains etc)
2. Users can also rate different places on a scale of 1-5.
3. Users profile (geographical location, places already visited etc are already stored in his profile)
4. Based on user's choice and other heuristics(rating etc), a set of places is recommended by the system.

# Answer
One of the best ways to benchmark such big systems is to use a service like Amazon Mechanical Turk (AMT). First you implement a user interface for everyday users where they could specify whether or not the recommendations are relevant. Then you submit this to Amazon Turk and let many people try it out.

You could further process the results of an Amazon Turk to really benchmark your system and obtain quantification of accuracy of it.

Team of Fei Fei Li used similar technique for benchmarking their Fine Grained segmentation algorithm. The paper is here: http://vision.stanford.edu/pdf/DengKrauseFei-Fei\_CVPR2013.pdf

Naturally using AMT won't give you a realtime solution, where you get a benchmark everytime a recommendation occurs, however you can prepare a subset of your dataset and let AMT guys evaluate the system using GUI you provide. Again, a sample data collection system is described here: http://ai.stanford.edu/~jkrause/papers/fgvc13.pdf

I have no intention of advertising it but AMT is also an economical workaround.
> 3 votes

# Answer
the basic strategy in \[supervised\] machine learning is to split the data into a "learning/training set" and a "test set". the algorithm when trained has no access to the test set which also acts something like a scientific control group. the algorithm attempts to learn a pattern. then you compare its performance on the data that it was "blind" to during training (also called "held out"), and if training/"generalization" occurred, the performance on the test data will be similar. briefly stated when there is a large drop in performance on training vs test data its called "overfitting" or "memorization" and the algorithm learned irrelevant details of the training data and did not "generalize". one "rule of thumb" balance on training vs test set is sometimes 80% vs 20% ie 4/5ths of the data is used for training and 1/5th is for test.
> 1 votes

---
Tags: machine-learning, recommendation-systems
---


# Question
Title: Is the image of a total, non-decreasing function decidable?
This is an exercise I've been struggling with for a while:

> Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x \> y.\ g(x) \geq g(y)$. Is the image $I\_g$ of $g$ a recursive set?

Intuitively, I know that the image $I\_{g}$ is not recursive, as $g$ is not strictly monotonic. In fact, it's because that $g$ is not strictly monotonic that $g$ could be a constant function so testing if $y \in I\_{g}$ may not finish as it could be that $\forall x, g(x) = c$, $c$ being a constant s.t. $c \< y$. Then, testing if there is an $x$ s.t. $g(x) = y$ incrementing $x$ as the $g(x) \< y$ may go forever. On the other hand, it could be that after a while, (for a sufficiently greater $x$) it happens that $g(x) \> c$ and $g(x) = y$. If it were stricly monotonic, though, then it would be recursive as I would be able to test if $y = g(x)$ incrementing $x$ until the equality is satisfied or $g(x) \> y$ (then $g(x)$ wouldn't get stuck in the same value because $x\_1 \> x\_2$ implies $g(x\_1) \> g(x\_2)$).

However, I haven't been able to prove this formally. Can this intuition become part of a formal proof? Or at least could you give me some help in proving it in some other way? A hint or some outline of a proof would be great.

# Answer
If $g$ is computable, its range is decidable. If $g$ is bounded, let $m$ be the maximum value in its range. Note that this number is not computable from a description of $g$ but it exists and we are only required to determine whether $g$'s range is computable, not whether the problem "Given $x$ and a description of $g$, determine whether $x$ is in the range of $g$" is decidable. Now, to decide if $x$ is in the range, reject if $m$ exists and $x\>m$; otherwise, start computing $g(0), g(1), \dots$. If you find that $g(y)=x$ for some $y$, then accept; otherwise, by monotonicity you will find that $g(y)\>x$ for some $y$ and reject.

If $g$ is not computable, its range may or may not be decidable. For example, let $M\_0, M\_1, \dots$ be an enumeration of all Turing machines and let $$g(x) = |\\{i\mid i\leq x \text{ and }M\_i(0)\text{ halts}\\}|.$$ The range is either all positive integers or all non-negative integers, depending on whether the machine with code zero halts. Whichever of those two sets really is the range of $g$, it is decidable (again, we're not being asked to decide which of these two cases is true; one of them must be). However, if we define $g(0)=0$ and $$g(i+1) = \begin{cases} g(i)+1 & \text{if }M\_i(0)\text{ halts}\\ g(i)+2 &\text{otherwise,}\end{cases}$$ then the range of $g$ is undecidable: an algorithm that could find the "gaps" would let you solve the zero-input halting problem.
> 1 votes

# Answer
I am assuming in my answer that $g$ is to be taken as computable, given the comments in the question. For non-computable $g$ see David's answer.

There are two answers:

1. There is no *uniform* decision procedure for membership in the image of a non-decreasing function. For suppose we had a decision procedure $P$ which would decide whether $n \in I\_g$ on input $\langle\ulcorner g \urcorner, n\rangle$. (Here $\langle\ulcorner g \urcorner$ is a suitable encoding of the Turing machine that computes $g$.) Then we could implement the Halting oracle as follows. Given a Turing machine $T$ let $g$ be $$g(n) = \begin{cases} 1 & \text{if $T$ halts in $\leq n$ steps}\\ 0 & \text{if $T$ does not halt in $\leq n$ steps}\\ \end{cases} $$ Clearly, $g$ is a monotone map and so we would have $$\text{$T$ halts} \iff P(\langle\ulcorner g \urcorner, 1\rangle).$$
2. For each such $g$ its image is decidable, but *non-uniformly* in $g$. (This means my proof will somewhere make a non-computable step.) Consider any non-decreasing $g$. Then either $I\_g$ is finite or $I\_g$ is infinite (that was the non-computable step):

* if $I\_g$ is finite then it is recursive
    * if $I\_g$ is infinite then we can use the usual trick: given and $n$, enumerate the values $g(0), g(1), g(2), \ldots$ and wait until they get larger than $n$, which they will as $I\_g$ is infinite. Once they do, see whether $n$ has been enumerated.
> 2 votes

# Answer
Note: $\\;\\;\\;$ This answer is wrong for the reason David mentions. $\\:$ (I was assuming that $g$ is computable.)

$\operatorname{Range}(\hspace{.02 in}g)\\:$ is bounded $\\;\\;\\; \implies \\;\\;\\;$ $\operatorname{Range}(\hspace{.02 in}g)\\:$ is finite $\\;\\;\\; \implies$
$\operatorname{Range}(\hspace{.02 in}g)\\:$ is a decidable set $\\;\\;\\; \iff \\;\\;\\;$ $I\_g$ is a recursive set

$\operatorname{Range}(\hspace{.02 in}g)\\:$ is not bounded $\\;\\;\\; \iff \\;\\;\\; (\hspace{.02 in}\forall y\in \mathbb{N})(\exists x\in \mathbb{N})(\hspace{.04 in}y\leq g(x)) \\;\\;\\; \implies$
testing if there is an x s.t. $g(x)=y$ incrementing x as the $g(x)\<y$ will eventually halt $\\;\\;\\; \implies$
"output yes or no depending on whether or not that found an x s.t. $g(x)=y$"
is a decision procedure for $\\:\operatorname{Range}(\hspace{.02 in}g)$
$\implies \\;\\;\\;$ $\operatorname{Range}(\hspace{.02 in}g)\\:$ is a decidable set $\\;\\;\\; \iff \\;\\;\\;$ $I\_g$ is a recursive set
Therefore $I\_g$ is a recursive set.
> 0 votes

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


# Question
Title: Lower bound on running time for solving 3-SAT if P = NP
Is there a lower bound on the running time for solving 3-SAT if P = NP. For instance, is it known that 3-SAT can't be solved in linear time? What about quadratic?

# Answer
> 6 votes
These are some of the best time and space bounds known. In this area the research has gone to the direction of giving bounds in both time and space. My understanding is that superlinear time bounds without a space constraint are not known.

Time-Space Lower Bounds for Satisﬁability Lance Fortnow, Richard Lipton, Dieter van Melkebeek

> We establish the ﬁrst polynomial time-space lower bounds for satisﬁability on general models of computation. We show that for any constant $c$ less than the golden ratio there exists a positive constant $d$ such that no deterministic random-access Turing machine can solve satisﬁability in time $n^c$ and space $n^d$, where $d$ approaches 1 when $c$ does.

---
Tags: complexity-theory, satisfiability, lower-bounds
---


title: Most common subset of size $k$

text:
# Question
Title: Most common subset of size $k$
I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size is as large as possible.

For example if I have:

```
s1 = {A, B, C   }
s2 = {A, B, C, D}
s3 = {   B, C, D}

```

Then the most common subset of size $\ge k=2$ is {B, C}. As another example, if I have:

```
s1 = {A, B, C  D}
s2 = {A, B, C, D}
s3 = {   B, C, D}

```

Then the most common subset of size $\ge k=2$ is {B, C, D}. It's important that in this instance the algorithm would give me {B, C, D} and not {B, C}, {B, D} etc. Note that I'm not interested in the longest common subset (a different problem), I'm interested in the longest most common subset if you will. I also don't care about enumerating all the different subsets, I just want to find the most common.

Is there an efficient algorithm for this problem?

I have an algorithm for this problem, but I don't think it's very efficient. For $k=2$ I enumerate all subsets of size 2 and count how many times each one appears in the collection. If the most-frequently occurring pair is more frequently occurring than any other pair then that must be the most common subset. If there is more than one with the same (maximum) frequency then I look at the sets they are contained in. If these overlap exactly then I take the union of the pairs and that gives me the most common subset (with size \> 2).

I think this could be related to the maximum clique problem but I'm not certain.

Note that just taking the intersection does not give the correct answer. For instance, if I have

```
s1 = {A, B      }
s2 = {      C, D}
s3 = {A,    C, D}

```

then the intersection is the empty set, but the most common subset is {C, D}.

# Answer
This problem is known as frequent itemset mining, or more precisely, maximal itemset mining. You can take a look at the Apriori algorithm and the FP-Growth algorithm.
> 2 votes

---
Tags: algorithms, graphs, sets, data-mining
---


# Question
Title: Optimal algorithm to traverse all paths in the order of shortest path
I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path.

The simplest way that comes to mind is to do a depth-first search (DFS) for all paths, accumulating their edge costs as I traverse the paths, and then doing an NlogN sort on the result.

But I wondering if there is a better way to do this task. Are there any algorithms that could optimize this problem (combining DFS and a shortest path algorithm such as Dijkstra's maybe?).

# Answer
The goal is to find all paths from $s$ to $t$ in a directed, acyclic graph with edge costs. Let $n$ the number of nodes, $m$ the number of edges and $p$ the number of $s$-$t$-paths. Let's look at what we have.

### Naive enumeration

1. Use any graph traversal from $s$ to find all paths.
2. Sort them by length.

You can interleave the steps, but you'll end up with runtime $\Omega(n + p \log p)$ if there are $n$ nodes and $p$ paths.

Note that this algorithm is easy to parallelise.

### Eppstein's Algorithm \[1\]

This one has runtime $O(m + n \log n + p)$ (from skimming the paper, I assume the bound is sharp, i.e. $\Theta$ holds). Note that paths are not represented explicitly.

I have no idea how well this algorithm can be parallelised.

### Lower bounds

First of all, $p \in \Omega(2^n)$ in the worst case even in DAGs, see for instance this class of graphs:

<sup>\[source\]</sup>

Note that all nodes have small out-degree and all paths have the same length.

Therefore, $p$ dominates any algorithm for this problem (in the worst case) if we can not make further assumptions.

When you go for a traversal over all paths, you clearly have runtime $\Omega(p)$.

### Conclusion

Eppstein's algorithm is asymptotically optimal even in the setting you describe. However, asymptotic analysis at this level is rough and hides "extra" work that may or may not pay off in practice (since $n$ does *not* tend to infinity). The naive version may very well be competitive in an application, depending on $n$, $m$ and $p$, and maybe even structural features.

Another thing to keep in mind is that above figures are all worst-case but you are probably after average runtime on some specific input set².

TCS papers are unlikely to contain a rigorous analysis that helps you decide (and it's hard to do, too). Your question reads as if your goal is a real-world application, so I recommend a pragmatic approach. If the naive approach is too slow for you, try parallelising it. If that is still to slow, you can invest the time, implement Eppstein and run some tests.

---

1. Finding the k Shortest Paths by D. Eppstein (1998) \[preprint\]
2. My group developed a method for semi-automated average-case analysis and a tool to perform it. Have a look, maybe it can help you find out more about performance on your data.
> 6 votes

---
Tags: algorithms, graphs, shortest-path, search-algorithms
---


# Question
Title: Transition systems that satisfy LTL but not CTL, and vice versa
I am learning about temporal logic and model checking systems. One conceptual exercise that I am struggling with is how to create a transition system which satisfies only *one* of two given properties, when one is in LTL and one is in CTL. For example:

* Find a transition system that satisfies only one of the following two properties: $FGp$, $AFEGp$
* Find a transition system that satisfies only one of the following two properties: $FGp$, $EFEGp$
* Find a transition system that satisfies only one of the following two properties: $GFp$, $AGEFp$

How should I begin when trying to reason about these types of problems? In general, is it easier to design transition systems for LTL properties or CTL properties? Or does it depend on the situation?

Any insight would be appreciated!

# Answer
Technically, LTL and CTL are incomparable in their differentiating power over Kripke structures. So intuitively, it shouldn't be easier to design one or the other.

However, most people tend to find it easier to think in linear time. Making sure a certain property holds for all paths is easier than studying a branching-time property. In particular, this is because a counter-example for the satisfaction of an LTL formula is a path, whereas a counterexample for a CTL formula may be a tree.

To demonstrate how to approach the questions at hand, let's consider the first one. First, consider what the formulas mean:

$FGp$ means "in every path, after a finite prefix, $p$ always holds".

$AFEGp$ means "in every path, after a finite prefix, a state is reached from which there exists a path in which $p$ is always true."

Now, if $FGp$ holds, then $AFEGp$ must also hold, because in every path, eventually a state is reached from which $Gp$ holds. Thus, our search should restrict to finding a system which satisfies $AFEGp$, but not $FGp$.

To achieve this, we need to at least have a state that satisfies $Gp$, so let's start with that. Take the state $A$ to have the transition $A\to A$, and $A$ is labeled with $p$. Let's also have $A$ as the initial state (this is arbitrary). So far, this system also satisfies $FGp$, so now we fix that by adding a "bad path": we add a state $B$, labeled by $\neg p$ with the transitions $A\to B$ and $B\to A$.

The path $A,B,A,B,...$ does not satisfy $FGp$, so this is good. However, every path eventually reaches $A$, in which $EGp$ is true, so $AFEGp$ holds, and we are done.
> 5 votes

---
Tags: logic, model-checking, linear-temporal-logic, computation-tree-logic
---


# Question
Title: Is regularity of the language accepted by a given Turing machine a semi-decidable property?
Given is the definition of a general problem: $\\{ \langle M, S\rangle \mid M \text{ is a } TM, L\_M \in S\\}$. In words: Given a TM M, does M decide a language that is an element of the given set of languages S?

I'm stuck with the following instance of that problem: $L = \\{ \langle M \rangle \mid M \text{ is a } TM, L\_M \in \mathrm{REG}\\}$. I have found proof that it is undecidable, however I'm stuck at finding if it's recognizable (synonyms: Turing-acceptable, semidecidable, ...) or not.

The problem in words means: Given a TM M, does the TM decide a language that is an element of REG (the set of regular languages)?

To prove a language is not semi-decidable, I would try to prove that it's complement is semi-decidable and that the language is not decidable (which I did by reduction from the Halting-problem).

To prove it is semi-decidable, I would prove it by reduction to the $A\_{TM}$, which is semi-decidable.

I have tried both for this problem, but I get stuck / lose my way of thinking at every try ... Some directions would be greatly appreciated!

# Answer
You have a good idea for proving that $L$ is not semi-decidable but it's not going to work since neither $L$ *nor* $\overline{L}$ are semi-decidable. Intuitively, how can saying after finite time "this language is not regular" be easier than "this language is regular" -- you can only inspect finitely many inputs, and all finite languages are regular (thus we can not separate REG from other classes on finite samples).

So we are left with our basic device: reduction from a non-semi-decidable language. The canonical one is the complement of the halting problem, i.e.

$\qquad\displaystyle \overline{K} = \\{ \langle M \rangle \mid M(\langle M \rangle) \text{ loops}\\}$.

Now we have to define a function for every $M$ whose accepted language is (non-)regular depending on whether $M$ halts on itself in order to establish the contradiction.

So, for any fixed TM $M$, define the following function¹:

$\qquad\displaystyle f\_M(w) = \begin{cases} 1, & w = a^n b^n \land M(\langle M \rangle) \text{ terminates after at most $n$ steps} \\ 0, &\text{else} \end{cases} $

The function $f\_M$ is clearly computable for any $M$; just check the form of the input and simulate $M$ for $n = \frac{|w|}{2}$ steps if necessary. Note furthermore that given $\langle M \rangle$, we can compute $\langle f\_M \rangle$; such compilation is possible because we have (or can assume) a Gödel numbering.

Now we have what we always want when reducing, the equivalence of doom:

$\qquad\displaystyle \langle M \rangle \in \overline{K} \iff \mathcal{L}(f\_M) = \emptyset \iff \mathcal{L}(f\_M) \in \mathrm{REG}$,

since $\mathcal{L}(f\_M) = \\{a^n b^n \mid n \geq N \\} \not\in \mathrm{REG}$ if $M(\langle M \rangle)$ halts after $N$ steps, i.e. $\langle M \rangle \in K$.

Thus, if we had a semi-decider for your $L$, we could semi-decide $\overline{K}$ which contradicts what we know.

---

1. For ease of notation I use strings as inputs; of course, we'd work on naturals using some computable bijection.
> 3 votes

---
Tags: formal-languages, computability, turing-machines, semi-decidability
---


# Question
Title: Is the set of Gödel numbers of computable constant functions recursively enumerable?
I've been working on the following exercise:

> $S = \\{ x | f\_x \text{ is constant} \\}$. Is $S$ recursively enumerable?

Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a computable function.

---

**Intuitively**, I think that to check if $S$ is constant, I would have to check if $f\_x$ stops for every input. That procedure would run forever.

**Important:** Same thing about $\overline{S}$, if some $f\_x$ is undefined for every input $y$ (it would not be constant, as far as I understand, **it is constant if it has the same image for all input values**) then I would not be able to list $f\_x$ in an enumeration of $\overline{S}$.

In fact, suppose $\forall x,fx$ is undefined. This $f\_x$ is computable - a TM can be constructed that loops forever. How can you determine that $f\_x$ is not constant? There will be no input for which $f\_x$ halts. Therefore, we cannot check for equality of $x\_1$ and $x\_2$ to determine that is not constant. Then, we can't list this $TM\_x$ in the enumeration.

A solution in which this $f\_x$ was put at the beginning of the enumeration was suggested. But there are infinitely many $TMs$ that are undefined for all inputs. Consequently, I can't put them at the beginning of the enumeration as other $TMs$ won't be enumerated.

---

**I tried to** reduce the *Halting Problem* to this problem without success. I believe that both $S$ and $\overline{S}$ are not r.e. (see my intuitive thoughts above).

How would you solve this problem?

# Answer
Your intuition is good: checking whether $x \in S$ is stronger than checking $x \in K$ ($K$ the halting problem, i.e. $K = \\{ x \mid f\_x(x) \text{ halts}\\}$). In other words,

$\qquad\displaystyle \langle \operatorname{sgn} \circ f\rangle \in S \implies f \in K$.

However, the reverse does not hold and no similar implication works for $\overline{K}$, the reduction partner we really want (as it's not semi-decidable).

---

A small interlude: the title you chose does not actually fit the question! The set of all constant functions *is* in fact recursively enumerable, e.g. by

$\qquad\displaystyle \varphi\_i(x) = i$

which is clearly a computable function. Many sets of functions are enumerable like this, but not all.

What you are really asking is: given a Gödel numbering (e.g. an encoding of all Turing machines), what about the set of all *indices* (read: programs) that compute this here set of functions? That's another thing entirely because of the properties such a Gödel numbering has. The distinction is important, see e.g. here.

---

The basic idea for a reduction is always this: build a function that depends on $x$ and whose encoding is in $S$ if and only if $x \in \overline{K}$ -- then we got a deal.

So, consider

$\qquad\displaystyle g\_x(n) = \begin{cases} n, &f\_x(x) \text{ halts after at most $n$ steps } \\ 1, &\text{else} \end{cases} $

which is clearly computable. Note furthermore that given $x$, we can compute $y$ with $f\_y = g\_x$; such compilation is possible because we have (or can assume) a Gödel numbering. Now, clearly

$\qquad \langle g\_x \rangle \in S \iff x \in \overline{K}$

holds; thus $S$ can't be semi-decidable since $\overline{K}$ would then be semi-decidable, too, contradicting what we know.
> 3 votes

---
Tags: computability, semi-decidability
---


# Question
Title: What are common techniques for reducing problems to each other?
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L\_1$ is at least as hard as some other problem $L\_2$ by mapping instances from $L\_2$ to solution-equivalent ones in $L\_1$. Essentially, we show that any solver for $L\_1$ can also solve $L\_2$ if we allow it to use the reduction function as preprocessor.

I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?

What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

# Answer
> 21 votes
# The Special Case

Assume we want to show $L\_1 \leq\_R L\_2$ with respect to some notion of reduction $R$. If $L\_1$ is a *special case* of $L\_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case.

In "practice", we are given $L\_2$ and are stuck with the problem of picking a good reduction partner $L\_1$, i.e. finding a special case of $L\_2$ that has proven to be $R$-hard.

## Simple Example

Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.

## Simple exercise problem

Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.

> 3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.

## Example

Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.

We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate

$\qquad \displaystyle f(A) = \begin{cases} \left(A, \frac{1}{2}\sum\_{a \in A} a\right) &, \sum\_{a \in A} a\mod 2 = 0 \\ \left(A, 1 + \sum\_{a \in A} |a|\right) &, \text{else} \end{cases}$

where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.

## Exercise Problem

Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

Show that LONGEST-PATH is NP-hard.

> HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
> Note in particular how reducing from HAMILTON-PATH requires more work.

# Answer
> 16 votes
# Leveraging a known nearby problem

When faced with a problem that feels hard, it is often a good idea to try to search for a similar problem that is already proven hard. Or, perhaps you can immediately see that a problem is very similar to a known problem.

## Example problem

Consider a problem

$$\text{DOUBLE-SAT} = \\{ \varphi \mid \varphi \text{ is a boolean formula with at least 2 satisfying assignments } \\}$$

we wish to show is $\mathsf{NP}$-complete. We quickly note that it is very close to a problem we already know is hard, namely the satisfiability problem (SAT).

The membership to $\mathsf{NP}$ is straightforward to show. The certificate is two assignments. Clearly, it can be checked in polynomial time whether the assignments satisfy a formula.

$\mathsf{NP}$-hardness follows from a reduction from $\text{SAT}$. Given a formula $\varphi$, we modify it by introducing a new variable $v$. We add a new clause $(v \vee \neg v)$ to the formula. Now, if $\varphi$ is satisfiable, it will be satisfiable with both $v = \perp$ and $v = \top$. Hence, $\varphi$ has at least 2 satisfying assignments. On the other hand, if $\varphi$ is not satisfiable, it will definitely not become satisfiable regardless of the value of $v$.

It follows that $\text{DOUBLE-SAT}$ is $\mathsf{NP}$-complete, which is what we wanted to show.

## Finding nearby problems

Reducing problems is kind of an art, and experience and ingenuity are often needed. Fortunately, many hard problems are already known. Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness is a classic one with its appendix listing many problems. Google Scholar is also a friend.

# Answer
> 6 votes
In computability, we often investigate sets of Turing machines. That is, our objects are functions and we have access to a Gödel numbering. That's great because we can do pretty much what we want with the input function, as long as we remain computable.

Assume we want to show that $L$ is not decidable. Our goal is to get to the equivalence of doom

$\qquad \langle M \rangle \in K \iff \langle f\_M \rangle \in L$

with $K = \\{ \langle M \rangle \mid M(\langle M \rangle) \text{ halts} \\}$ the halting problem (or any other undecidable language/problem).

Thus, we need to come up with a computable¹ mapping $\langle M \rangle \mapsto \langle f\_M \rangle$ so that $f\_M$ is always computable. This is a creative act informed by the equivalence of doom. See some examples to get an idea of how this works:

The same works for showing that $L$ is not semi-decidable by choosing non-semi-decidable languages as reduction partner, e.g. $\overline{K}$:

---

1. This is where the Gödel numbering comes in: we get computability of this mapping (usually) for free.

# Answer
> -2 votes
it depends on the complexity classes involved, and whether one wants to reduce from a given $A$ to an unknown $B$, or an unknown $B$ to a given $A$. the common scenario is to prove problems NP Hard or NP Complete. a common technique is to construct "gadgets" in one domain that behave in a certain way, mimicking the behavior of another domain. for example to convert SAT to vertex cover, one constructs "gadgets" in vertex cover that behave similarly to clauses of SAT, eg in the following slide show: NP Complete reductions by Krishnamoorthy (also with an example for Hamilton path).

a useful strategy is to work from large compilations of problems from the complexity class in question and find the "apparent nearest problems" to the problem being studied. an excellent reference along these lines is Computers and Intractability, a guide to the theory of NP completeness, Garey and Johnson organized by different problem types.

---
Tags: complexity-theory, computability, reductions, proof-techniques, reference-question
---


title: Finite Automata Input Confusion

text:
# Question
Title: Finite Automata Input Confusion
I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs. I am wondering what would happen when you have the input string 'abba' with this automata:

The possible computations I have so far are

q0, q0, q0, q0, q0

q0, q0, q1, q2, ??

q0, q0, q0, q1, ??

Would anyone be able to fill in the '??'s in this automata and be able to explain why they occur?

# Answer
> 0 votes
If you're at a state $q$ reading $\alpha$ and there is no outgoing edge labeled $\alpha$, then there is way to extend the computation path. In view of that, the only valid computation path upon reading $abba$ is $q\_0,q\_0,q\_0,q\_0,q\_0$; in fact, the same is true for any word ending in $a$, whose computation paths are of the form $q\_0,\ldots,q\_0$. Words ending in $b$ have the additional computation path $q\_0,\ldots,q\_0,q\_1$, and words ending in $bb$ have the additional computation path $q\_0,\ldots,q\_0,q\_1,q\_2$, making three in total.

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


# Question
Title: Understanding a proof for the existance of a non-computable function
For school, we have a proof that some functions are not Turing computable. The example is: $$ G(k) = \begin{cases} f\_k(k) + 1 & \text{ if $f\_k(k)$ is defined}, \\ 1 & \text{ otherwise}.\end{cases} $$

Claim: $G$ is non computable.

Proof: In view of obtaining a contradiction, let's say $G$ is computable, say by the $k$th Turing machine. Give the encoding of this $k$th Turing machine as an argument for $G$. This leads to a contradiction: if $f\_k(k)$ is defined, then $f\_k(k)$ is not equal to $g(k) = f\_k(k) + 1$. Else $f\_k(k)$ is undefined and not equal to $g(k) = 1$.

I don't understand the contradiction, help please...

# Answer
> 5 votes
The contradiction reached is that $0 = 1$ which violates one of Peano's axioms. Assume $G$ is computed by the $j$-th Turing machine. Observe that $G$ is everywhere defined. Then $$f\_j(j) = G(j) = f\_j(j) + 1$$ and by canceling $f\_j(j)$ on both sides we get $$0 = 1.$$

---
Tags: computability, turing-machines, undecidability
---


title: Is DSPACE properly contained in NSPACE?

text:
# Question
Title: Is DSPACE properly contained in NSPACE?
It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$? In other words, is the containment relation proper or not? Wikipedia says the first one, while the ComplexityZoo says the other one.

# Answer
> 5 votes
It's open whether $\mathsf{DSPACE}(\log n) = \mathsf{NSPACE}(\log n)$, which is the $\mathsf{L}=\mathsf{NL}$ question. As far as I know, the closest thing we can say are theorems by Savitch $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}(f(n)^2)$ and Immerman–Szelepcsényi's ($\mathsf{NSPACE}$ is closed under complement).

Also see AndrewK's answer regarding the subset symbol, I think this is the issue here.

# Answer
> 2 votes
It's not a dumb question. One thing to note is that not all literature agrees on how exactly to use the different subset symbols. It is entirely plausible that two sources could be using the same symbols to mean different things, thereby communicating the same information! Confusing, isn't it?

Pending review: ~~For an intuitive understanding, think about how non-deterministic TMs theoretically work. They can always accomplish the same tasks in the same memory spaces, and they can often also accomplish the same tasks in smaller memory spaces. This means more spaces are available to a non-deterministic TM. NSPACE contains more than just DSPACE. DSPACE is a proper/strict subset of NSPACE.~~

---
Tags: complexity-theory, complexity-classes, space-complexity
---


# Question
Title: Calculating eigenvalue gap of a torus graph
Consider a two-dimensional grid with wrap-around edges (a doughnut-shaped graph). I need to calculate the second-largest eigenvalue of the adjacency matrix. Is there a faster way of computing it for such a special graph than a general method such as the "eigs" function in MATLAB?

# Answer
> 3 votes
Suppose that the torus is $n\times n$. Let $\omega = e^{2\pi i/n}$ be a primitive $n$th root of unity, and let $v\_{\alpha,\beta}$ be the $n\times n$ vector given by $v\_{\alpha,\beta}(i,j) = \omega^{i\alpha+j\beta}$. Using $A$ for the adjacency matrix of the torus (indexed by pairs $(i,j) \in \mathbb{Z}\_n$), $$ \begin{align\*} (Av\_{\alpha,\beta})(i,j) &= v\_{\alpha,\beta}(i+1,j) + v\_{\alpha,\beta}(i-1,j) + v\_{\alpha,\beta}(i,j+1) + v\_{\alpha,\beta}(i,j-1) \\ &= v\_{\alpha,\beta}(i,j) (\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}). \end{align\*} $$ In other words, $v\_{\alpha,\beta}$ is an eigenvector with eigenvalue $\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}$. It is not hard to check that the $n^2$ vectors $v\_{\alpha,\beta}$ are linearly independent, and so they form a basis of eigenvectors for $A$. The eigenvalues are $$ \lambda\_{\alpha,\beta} = \omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta} = 2\left(\cos \frac{\alpha2\pi}{n} + \cos \frac{\beta2\pi}{n}\right). $$ For $\alpha \in \\{0,\ldots,n-1\\}$, the function $\cos \frac{\alpha2\pi}{n}$ reaches its maximum $1$ at $\alpha = 0$, and otherwise its second largest value is attained at $\alpha=1$ and $\alpha=n-1$. Therefore the second-largest eigenvalue is $2 + 2\cos \frac{2\pi}{n}$. More generally, for a $d$-dimensional grid, the second-largest eigenvalue is $2(d-1) + 2\cos \frac{2\pi}{n}$, and the eigenvalue gap is $2-2\cos \frac{2\pi}{n} = \Theta(\frac{1}{n^2})$.

---

More generally, the $n\times n$ torus is the cartesian product of the $n$-cycle with itself. It is well-known that if $G$ has eigenvalues $\lambda\_i$ and $H$ has eigenvalues $\mu\_j$ then the eigenvalues of the cartesian product of $G$ and $H$ are $\lambda\_i + \mu\_j$ (the proof follows the computation above, replacing $\omega^{i\alpha}$ with an arbitrary eigenvector of $G$, and $\omega^{j\beta}$ with an arbitrary eigenvector of $H$). It follows that the eigenvalue gap of the product is the minimum between the eigenvalue gaps of $G$ and $H$.

---
Tags: graphs, linear-algebra
---


# Question
Title: 0/1 Integer Programming and Karp's Reduction
I have been reading Karp's famous paper on the NP-Completeness of different problems, *Reducibility among combinatorial problems*, and I have a question on the reduction from *SAT* to *0/1 Integer Programming* defined there.

The problem *0/1 Integer Programming* is defined as:
Input: Integer matrix $A$ and integer vector $d$
Property: There exists a 0/1 vector $x$ such that $Ax=b$.
Let $B$ be a boolean formula in CNF with $p$ variables $x\_1,\dots, x\_p$ and $n$ clauses $C\_1,\dots,C\_n$. The reduction from *SAT* should work like this ($C\_i$ is the $i^{\text{th}}$ clause of the boolean formula): $$ a\_{ij} = \begin{cases} 1 &\text{if } x\_j \in C\_i \\ -1 &\text{if } \bar{x}\_j \in C\_i\\ 0 &\text{otherwise} \end{cases} $$ and $$ b\_i = 1- (\text{ the number of complemented variables in } C\_i ). $$ Now if I use this procedure on the satisfiable formula $(x\_1 \vee x\_2 ) \wedge (x\_1 \vee x\_3 ) \wedge (x\_2 \vee x\_3 )$, I get $$ A =\left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{array} \right), \text{ and } b = \left( \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right), $$ which has no 0/1 solution. So my question is:
Have I made a very silly mistake, or is Karp's original reduction faulty?

# Answer
> 5 votes
I believe there's a typo in Karp's definition of the problem. If we replace $Ax=b$ with $Ax \geq b$, the reduction goes through as is. The easiest way I can think of to show the hardness of your problem (the one as written in Karp's paper), is via 1-in-3 SAT or via hypergraph perfect matching.

---
Tags: np-complete, reductions
---