العلاقة بين حجم الدائرة وحجم الصيغة في نص Sipser

Question

href="https://math.mit.edu/~siper/book.html" rel="nofollow noreferrrer"> نص sipser الطبعة الثالثة) يحتوي على دليل على وجود 3-SAT هو NP كامل بناء على دوائر منطقية. يحتوي جزء من الدليل على ملاحظة أن التخفيض من الدائرة إلى الصيغة المنطقية يمكن القيام به في وقت متعدد الحدود.

السؤال الأول: هل صحيح أن نقول أنه إذا كانت الدائرة C من حجم متعدد الحدود موجودة، فيجب أن توجد هناك صيغة $ \ varphi $ حجم متعدد الحدود حيث c هو راض إذا وفقط إذا $ \ varphi $ راضي؟

السؤال الثاني: هل الصيغة المنطقية $ \ varphi $ لا يزال حجم متعدد الحدود إذا كان C من حجم متعدد الحدود و C مشتقة من الحتمية تورينج آلة م؟ يبدو أن هذا هو موصوف في دليل على النظرية السابقة في Sipser حيث (عن طريق بناء C من لوحة م) يتم عرضه أنه إذا كان $ \ mbox {a $ \ in time $ (t (n)) $ مقابل $ t (n) \ geq n $ and $ n \ in \ mathbb {n} $} $ ثم لدى تعقيد الدوائر $ O (T ^ 2 (n)) $ .

Answer 1

نعم، هذا صحيح.شاهد TSESITIN تحويل ، والتي تصف كيفية.لا يهم كيف تم بناء الدائرة $ C $ .