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.
Does every Turing-recognizable undecidable language have a NP-complete subset?
cc.complexity theory;np hardness;complexity classes;np;decidability
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. 