هو CO-P عدل بشكل متكرر؟

Question

p هو إعادة، ولكنه هو استكمال فئة اللغات التي يتم حلها في وقت متعدد الحدود بشكل متكرر؟

إذا كانت كلاهما في ذلك، فهذا يجعل P عريض؟

Answer 1

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