10
$\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$

1 Answer 1

22
$\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$
1
  • $\begingroup$ Thanks for the answer and the useful pointer to Mahaney's theorem! $\endgroup$ Jan 22, 2013 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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