CO-P é recursivamente enumerável?

Question

p é re, mas é o complemento da classe de idiomas decidível no tempo polinomial também recursivamente enumerável?

Se ambos são, então, isso torna P recursivo?

Answer 1

co- $ \ mathsf {p}=mathsf {p} $ .Para ver isso, escolha seu problema favorito $ a $ em co- $ \ mathsf {p} $ ,Deixe $ t $ ser uma máquina de Turing para o complemento da $ a $ (em $ \ mathsf {p} $ ) e construa uma nova máquina de Turing $ t '$ que simula $ T $ , aceita se $ t $ rejeita e rejeita se $ t $ Aceita.