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

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.

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.

• Thanks for the answer and the useful pointer to Mahaney's theorem! Jan 22, 2013 at 17:02