¿Es CO-P recursivamente enumerable?

Question

p es re, pero ¿el complemento de la clase de idiomas decidible en el tiempo polinomial también es recursivamente enumerable?

Si ambos son re, entonces esto hace que P recursive?

Answer 1

co- $ \ mathsf {p}=mathsf {p} $ .Para ver esto, elija su problema favorito $ a $ en co-span class="math-contenedor matemático"> $ \ mathsf {p} $ ,Deje que $ t $ sea una máquina de Turing para el complemento de $ a $ (en $ \ mathsf {p} $ ) y construir una nueva máquina de Turing $ t '$ que simula $ t $ , acepta si $ t $ rechaza, y rechaza si $ t $ acepta.