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.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityNo.
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.