هو CO-P عدل بشكل متكرر؟
-
29-09-2020 - |
سؤال
p هو إعادة، ولكنه هو استكمال فئة اللغات التي يتم حلها في وقت متعدد الحدود بشكل متكرر؟
إذا كانت كلاهما في ذلك، فهذا يجعل P عريض؟
المحلول
co- $ \ mathsf {p}=mathsf {p} $ .لرؤية هذا، اختر مشكلة المفضلة لديك $ $ في CO- $ \ mathsf {p} $ ،دع $ t تكون آلة تورينج لاستكمال $ $ (في $ \ mathsf {p} $ ) وبناء آلة تورينج جديدة $ T '$ التي تحاكي $ t $ ، يقبل إذا $ T $ الرفض، ويرفض إذا $ t $ يقبل.
لا تنتمي إلى cs.stackexchange