¿Cada lenguaje indecidible reconocible de Turing tiene un subconjunto NP-completo?

Respuestas:

21

No.

Los lenguajes indecidibles reconocibles por Turing pueden ser unarios (definir menos que , por lo que las únicas cadenas difíciles se componen únicamente de 0). El teorema de Mahaney dice que ningún lenguaje unario puede ser NP completo a menos que P = NP.x = 0000 0xLx=00000

Peter Shor
fuente
¡Gracias por la respuesta y el útil puntero al teorema de Mahaney!
veryltdbeard