# 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

### 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 ...
• 821
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,603
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]$: ...
• 730

Only top scored, non community-wiki answers of a minimum length are eligible