9
$\begingroup$

Does every Turing-recognizable undecidable language have a NP-complete subset?

The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an infinite decidable subset.

$\endgroup$
21
$\begingroup$

No.

Turing-recognizable undecidable languages can be unary (define $x \not\in L$ unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP.

$\endgroup$
  • $\begingroup$ Thanks for the answer and the useful pointer to Mahaney's theorem! $\endgroup$ – veryltdbeard Jan 22 '13 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.