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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Jan 22, 2013 at 16:48
-
$\begingroup$ Thanks for the answer and the useful pointer to Mahaney's theorem! $\endgroup$ Jan 22, 2013 at 17:02