الدوائر والصيغ لمرض

Question

هل صحيح أن تقول أن مشكلة الزمرة في $ P $ IFF موجودة عائلة من الدوائر المنطقية $C $ لتحديد الزمرة التي يحدها أحجامها من قبل متعدد الحدود؟وبناء على هذا السؤال هل يعني ذلك وجود مجموعة مكافئة من الصيغ المنطقي $ f $ لتحديد Clique التي تحد أحجامها بواسطة متعدد الحدود؟وإذا كان هناك مثل هذا $ f $ ، هل سيكون هناك اشتقامات صحيحة تستند إلى بديهيات المنطق الاقتراح من أي عضو في $ f$ إلى المقابلة صيغة ساذجة كبيرة لمرض الزمرة ؟

Answer 1

أخشى أن الإجابة على جميع أسئلتك هي خطأ:

• هناك لغات التي تقررها الدوائر المستمرة الحجم غير القابلة للاستحقاق.
• تم تخمينها أن $ \ mathsf {nc ^ 1} \ Neq \ mathsf {p} $ .
• يتم تخزينها أن $ \ mathsf {np} \ neq \ neq \ mathsf {conp} $ .