Todo idioma indecidível reconhecível por Turing possui um subconjunto NP-completo?

Todo idioma indecidível reconhecível por Turing possui um subconjunto NP-completo?

A questão poderia ser vista como uma versão mais forte do fato de que toda linguagem infinita reconhecível de Turing tem um subconjunto infinito e decidível.

Não.

Linguagens indecidíveis reconhecíveis por Turing podem ser unárias (defina menos que , portanto, as únicas cadeias difíceis são compostas apenas por zeros). O teorema de Mahaney diz que nenhuma linguagem unária pode ser NP-completa, a menos que P = NP.$x \not\in L$$x = 0000\ldots 0$