CO-Pは再帰的に列挙可能ですか?
-
29-09-2020 - |
質問
pはReですが、多項式時間で決定できる言語のクラスの補完も再帰的に列挙可能ですか?
両方が再発した場合、これはP再帰的な?
解決
co $ \ mathsf {p}=mathsf {p} $ 。これを確認するには、お気に入りの問題を選択します。 $ a $ co- $ \ mathsf {p} $ で、 $ t $ を $ a $ ( $ \ mathsf {p} $ )および新しいチューリングマシン $ t '$ をシミュレートする $ t $ は、 $ t $ の拒否を受け入れ、 $ t $ 受け入れます。
所属していません cs.stackexchange