# Tag Info

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
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

### 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 ...
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 ...
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