Est co-p récursivement énumérable?

Question

p est re, mais est le complément de la classe de langues enrichissable en temps polynomial, également extrêmement énumérable?

Si les deux sont alors reins, cela rend P récursif?

Answer 1

Co- $ \ mathsf {p}=mathsf {p} $ .Pour voir cela, choisissez votre problème préféré $ A $ en co- $ \ mathsf {p} $ ,Laissez $ t $ être une machine de Turing pour le complément de $ a $ (en $ \ mathsf {p} $ ) et construire une nouvelle machine Turing $ t '$ qui simule $ t $ , accepte si $ t $ rejette et rejette si $ t $ accepte.