Hot answers tagged

9 votes

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

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

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

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