9
votes
Accepted
Enumerating finite set of words with Hamming distance $1$
This problem is NP-complete.
The class of graphs in the question is equivalent to the cubical graphs *1, but this class contains grid graphs.
Because the Hamiltonian path problem in grid graphs is NP-...
- 206
4
votes
Accepted
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
This class was defined in Papadimitriou's original 1994 paper, that also introduced the class PPAD, and it is known as PPADS. There is an oracle separation between the two classes. For a recent paper ...
- 13.8k
2
votes
Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP
The equivalence you're talking about is a very coarse one. The DTM $A$ corresponding to an NTM $B$ in the obvious way will accept the same language as $B$, but it will do so vastly more slowly. Since ...
- 506
2
votes
Accepted
What if NP = coNP?
This got a bit too long for a comment, I might edit this to provide a more coherent answer at a later point.
There is this answer to Is it possible to construct an encryption scheme for which breaking ...
- 841
1
vote
Accepted
Short UNSAT Certificates for X3SAT
I can now prove my conjecture is false. The unsatisfiable 4 Pigeons in 3 Holes problem, when converted to linear, monotone X3SAT, does not have any completely blocked Conflict Clusters.
A conflict ...
- 519
1
vote
Accepted
Does the set $P$ contain only decision problems or also optimization problems?
SHORT ANSWER
By definition, P and NP are (infinite) sets of decision problems (more exactly, Languages, but let's keep it simple). Studying the decision problem version of computational problem is ...
- 2,723
1
vote
Cook's theorem and universal machine
what Papadimitriou and Yannakakis mean is something along the following lines. Consider the language L consisting of all triples <M,x,t> where M is a nondeterministic Turing machine, x is a ...
- 11
1
vote
Accepted
Can one find any solution to this matrix problem in polynomial time?
It seems the following very simple algorithm works as long as $\sum_x \text{row}[x]= \sum_y \text{col}[y]$:
...
- 775
Only top scored, non community-wiki answers of a minimum length are eligible