Chaque langage indécidable reconnaissable par Turing a-t-il un sous-ensemble NP-complet?

Chaque langage indécidable reconnaissable par Turing a-t-il un sous-ensemble NP-complet?

La question pourrait être considérée comme une version plus forte du fait que chaque langue infinie reconnaissable par Turing a un sous-ensemble décidable infini.

Non.

Les langages indécidables reconnaissables par Turing peuvent être unaires (définissez sauf si , de sorte que les seules chaînes difficiles sont composées uniquement de 0). Le théorème de Mahaney dit qu'aucun langage unaire ne peut être NP-complet à moins que P = NP.$x \not\in L$$x = 0000\ldots 0$