Como mostrar que o conjunto de máquinas que aceitam idiomas em

8

Gostaria da sua ajuda para provar que o idioma é decidível se .

L={M|L(M)NPP}
P=NP

Se , entendi que é a linguagem das máquinas de Turing vazias. Então é um problema - mas não é isso que está sendo perguntado, então fiquei confuso.P=NPLco-RE

Eu sei que, para mostrar , preciso mostrar o problema que é e também.P=NPNPCP

Qualquer ajuda? Obrigado!

Jozef
fonte

Respostas:

9

Há dois casos a considerar.

  1. Assuma isso P=NP. EntãoL={ML(M)}=. O idioma vazio é decidível; como nenhuma palavra pertence a ela, é trivial decidir se uma palavra pertence a ela ou não.

  2. Assuma isso PNP. Agora seu resultado segue diretamente do teorema de Rice .

Dave Clarke
fonte