الملكية الفكرية (التعقيد)

نبدأ بإثبات أن #SAT يقع في IP ، حيث:

${\displaystyle \#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \$ φ هي صيغة CNF تحتوي على k من القيم التي تحقق التعيينات.

لاحظ أن هذا يختلف عن التعريف العادي لـ #SAT ، حيث أنه مشكلة قرار ، وليس دالة.

نستخدم أولًا التحويل الحسابي لتحويل الصيغة المنطقية ذات n متغير، φ( _b₁ , ..., _{bₙ)، إلى متعددة حدود pφ(x₁} , _... , xₙ ) ، حيث تحاكي pφ الصيغة _{φ في} كونها تساوي 1 إذا كانت φ صحيحة _{، و0 فيما عدا ذلك ،} بشرط أن تكون قيم متغيرات pφ منطقية. تُحاكى العمليات المنطقية ∨ و∧ و¬ المستخدمة في φ في pφ _{باستبدال} المعاملات في φ كما هو موضح في الجدول أدناه _.

على سبيل المثال،${\displaystyle \phi =a\land (b\lor \neg c)}$ سيتم تحويلها إلى متعددة الحدود على النحو التالي:

${\displaystyle {\begin{aligned}p_{\varphi }&=a\wedge (b\vee \neg c)\\&=a\wedge \left(b*(1-c)\right)\\&=a\wedge \left(1-(1-b)(1-(1-c))\right)\\&=a\left(1-(1-b)(1-(1-c))\right)\\&=a-(ac-abc)\end{aligned}}}$

تؤدي العمليات ab و a ∗ b كل منهما إلى متعدد حدود بدرجة محدودة بمجموع درجات متعددات الحدود لـ a و b ، وبالتالي فإن درجة أي متغير هي على الأكثر طول φ.

ليكن F حقلاً منتهياً رتبته q > 2n ^؛ واشترط أيضاً أن تكون q على الأقل 1000. لكل i ≤ 0 ≤ n ، عرّف دالة fᵢ على F _، ذات معاملات${\displaystyle a_{1},\dots ,a_{i-1}\in F}$ومتغير واحد${\displaystyle a_{i}\in F}$: لـ 0 ≤ i ≤ n و لـ${\displaystyle a_{1},\dots ,a_{i}\in F}$يترك

${\displaystyle f_{i}(a_{1},\dots ,a_{i})=\sum \nolimits _{a_{i+1},\dots ,a_{n}\in \{0,1\}}p(a_{1},\dots ,a_{n}).}$

لاحظ أن قيمة f ₀ هي عدد التعيينات المُرضية لـ φ. f ₀ هي دالة فارغة، بدون متغيرات.

أما الآن، فيعمل بروتوكول #SAT على النحو التالي:

• المرحلة 0 : يختار المُثبت P عددًا أوليًا q > ²ⁿ ويحسب f0 _، ثم يرسل q و f0 إلى المُدقِّق V. يتحقق V من أن q عدد أولي أكبر من max(1000, ²ⁿ ₎ وأن f0 ( ) = _k .
• المرحلة الأولى : يرسل P معاملات f1 ( z ) كمتعددة حدود في z. يتحقق V من أن درجة f1 أقل من n وأن _f0 = f1 _{( 0} ) + f1 ( ₁ ). (إذا لم يكن الأمر كذلك، _يرفض V ₎ . ثم يرسل V عددًا عشوائيًا r1 من F إلى P.
• المرحلة الأولى : يرسل P معاملات${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$كدالة متعددة الحدود في _z . يتحقق V من أن درجة fᵢ أقل من n وأن${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})=f_{i}(r_{1},\dots ,r_{i-1},0)+f_{i}(r_{1},\dots ,r_{i-1},1)}$(إذا لم يرفض V ). الآن يرسل V رقمًا عشوائيًا r _i من F إلى P.
• المرحلة n+1 : تقييم V${\displaystyle p(r_{1},\dots ,r_{n})}$للمقارنة بالقيمة${\displaystyle f_{n}(r_{1},\dots ,r_{n})}$إذا كانت متساوية ، يقبل V ، وإلا يرفض V.

لاحظ أن هذه خوارزمية عملة عامة.

إذا كان لـ φ عدد k من التعيينات المُرضية، فمن الواضح أن V سيقبلها. أما إذا لم يكن لـ φ عدد k من التعيينات المُرضية، فإننا نفترض وجود مُثبت.${\displaystyle {\tilde {P}}}$يحاول هذا إقناع V بأن φ لديها k من التعيينات المُرضية. نُبين أن هذا لا يمكن تحقيقه إلا باحتمالية منخفضة.

لمنع V من الرفض في المرحلة 0،${\displaystyle {\tilde {P}}}$يجب إرسال قيمة غير صحيحة${\displaystyle {\tilde {f}}_{0}()}$إلى النقطة P. ثم، في المرحلة 1،${\displaystyle {\tilde {P}}}$يجب إرسال متعددة حدود غير صحيحة${\displaystyle {\tilde {f}}_{1}}$مع العقار الذي${\displaystyle {\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}()}$عندما يختار V قيمة عشوائية r1 لإرسالها _إلى P ،

${\displaystyle \Pr \left[{\tilde {f}}_{1}(r_{1})=f_{1}(r_{1})\right]<{\tfrac {1}{n^{2}}}.}$

وذلك لأنّ كثيرة الحدود في متغير واحد من الدرجة d على الأكثر لا يمكن أن يكون لها أكثر من d جذر (إلا إذا كانت قيمتها دائمًا تساوي صفرًا). لذا، فإنّ أي كثيرتي حدود في متغير واحد من الدرجة d على الأكثر _يمكن أن تكونا متساويتين فقط في d خانة. وبما أنّ | F | > 2n ^، فإنّ احتمال أن تكون r1 إحدى هذه القيم هو على الأكثر${\displaystyle n/2^{n}<n/n^{3}}$إذا كان n > 10، أو على الأكثر ( n /1000) ≤ ( n / n ³ ) إذا كان n ≤ 10.

بتعميم هذه الفكرة على المراحل الأخرى، لدينا لكل 1 ≤ i ≤ n إذا

${\displaystyle {\tilde {f}}_{i-1}(r_{1},\dots ,r_{i-1})\neq f_{i-1}(r_{1},\dots ,r_{i-1}),}$

ثم بالنسبة لـ r _i المختارة عشوائياً من F ،

${\displaystyle \Pr \left[{\tilde {f}}(r_{1},\dots ,r_{i})=f_{i}(r_{1},\dots ,r_{i})\right]\leq {\tfrac {1}{n^{2}}}.}$

هناك n مرحلة، لذا فإن احتمال أن${\displaystyle {\tilde {P}}}$يُعتبر V محظوظًا لأنه يختار في مرحلة ما قيمة r_{_i} مناسبة ، بحيث لا تتجاوز احتمالية قبولها 1/ n . لذا، لا يمكن لأي مُثبِت أن يُجبر المُدقِّق على قبولها باحتمالية أكبر من 1/ n . كما يتضح من التعريف أن المُدقِّق V يعمل في زمن متعدد الحدود احتمالي. وبالتالي، فإن #SAT ∈ IP .

لإثبات أن PSPACE مجموعة جزئية من IP ، نحتاج إلى اختيار مسألة كاملة في PSPACE وإثبات أنها تنتمي إلى IP . بمجرد إثبات ذلك، يتضح أن PSPACE ⊆ IP . يُنسب أسلوب البرهان الموضح هنا إلى آدي شامير .

نعلم أن TQBF تنتمي إلى فئة PSPACE-Complete . لذا، لنفترض أن ψ تعبير منطقي كمي :

${\displaystyle \psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]}$

حيث φ صيغة CNF. إذن Q _i مُكمِّم، إما ∃ أو ∀. الآن f _i هي نفسها كما في البرهان السابق، ولكنها الآن تتضمن مُكمِّمات أيضًا.

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i}(a_{1},\dots ,a_{m})=1&{\mathsf {Q}}_{i+1}x_{i+1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi (a_{1},\dots ,a_{i})]{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}}$

هنا، φ( a₁ , ..., aᵢ ₎ هي φ مع _{استبدال x₁ إلى xᵢ بـ a₁} إلى aᵢ . بالتالي _، f₀ هي القيمة _{المنطقية} لـ _ψ . ولتحويل ψ إلى صيغة حسابية، يجب استخدام القواعد _{التالية :}

${\displaystyle f_{i}(a_{1},\dots ,a_{i})={\begin{cases}f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\forall \\f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\exists \end{cases}}}$

بينما كما في السابق، نُعرّف x ∗ y = 1  −  (1  − x )(1 − y ).   

باستخدام الطريقة الموضحة في #SAT، نواجه مشكلة تتمثل في أن درجة متعددة الحدود الناتجة قد تتضاعف مع كل مُكمِّم، _وذلك لأي قيمة fᵢ . ولمنع ذلك، يجب علينا إدخال عامل اختزال جديد R يُخفِّض درجات متعددة الحدود دون تغيير سلوكها عند إدخال قيم منطقية.

والآن قبل أن نبدأ بالحساب${\displaystyle \psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]}$نقدم تعبيراً جديداً:

${\displaystyle \psi '={\mathsf {Q}}_{1}\mathrm {R} x_{1}{\mathsf {Q}}_{2}\mathrm {R} x_{1}\mathrm {R} x_{2}\dots {\mathsf {Q}}_{m}\mathrm {R} x_{1}\dots \mathrm {R} x_{m}[\varphi ]}$

أو بعبارة أخرى:

${\displaystyle \psi '={\mathsf {S}}_{1}y_{1}\dots {\mathsf {S}}_{k}y_{k}[\varphi ],\qquad {\text{ where }}{\mathsf {S}}_{i}\in \{\forall ,\exists ,\mathrm {R} \},\ y_{i}\in \{x_{1},\dots ,x_{m}\}}$

الآن، لكل i ≤ k، نُعرّف الدالة f _i . ونُعرّف أيضًا${\displaystyle f_{k}(x_{1},\dots ,x_{m})}$لتكون متعددة الحدود p ( x ₁ , ..., x _m ) التي يتم الحصول عليها عن طريق إجراء العمليات الحسابية على φ. الآن، من أجل الحفاظ على درجة متعددة الحدود منخفضة، نُعرّف f _i بدلالة f _i+1 :

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\forall ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)}$

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\exists ,\quad f_{i}(a_{1},\dots ,a_{i})=f_{i+1}(a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)}$

${\displaystyle {\text{If }}{\mathsf {S}}_{i+1}=\mathrm {R} ,\quad f_{i}(a_{1},\dots ,a_{i},a)=(1-a)f_{i+1}(a_{1},\dots ,a_{i},0)+af_{i+1}(a_{1},\dots ,a_{i},1)}$

الآن يمكننا أن نرى أن عملية الاختزال R لا تُغير درجة متعددة الحدود. ومن المهم أيضًا أن نرى أن عملية R _x لا تُغير قيمة الدالة على المدخلات المنطقية. لذا، فإن f ₀ لا تزال القيمة الحقيقية لـ ψ، لكن قيمة R _x تُنتج نتيجة خطية في x . كذلك، بعد أي${\displaystyle {\mathsf {Q}}_{i}x_{i}}$نضيف${\displaystyle \mathrm {R} _{x_{1}}\dots \mathrm {R} _{x_{i}}}$في ψ′ لتقليل الدرجة إلى 1 بعد إجراء العملية الحسابية${\displaystyle {\mathsf {Q}}_{i}}$.

والآن دعونا نصف البروتوكول. إذا كان n هو طول ψ، فإن جميع العمليات الحسابية في البروتوكول تتم على حقل بحجم لا يقل عن n ⁴ حيث n هو طول ψ.

• المرحلة 0 : P → V : يرسل P القيمة f ₀ إلى V. يتحقق V من أن f ₀ = 1 ويرفض إذا لم يكن كذلك.
• المرحلة الأولى : P → V : يرسل P _الدالة f1 ( z ) إلى V. يستخدم V المعاملات لتقييم f1 ₍ 0) و f1 ( ₁ ). ثم يتحقق من أن درجة متعددة الحدود لا تتجاوز n وأن المتطابقات التالية صحيحة:

${\displaystyle f_{0}(\varnothing )={\begin{cases}f_{1}(0)\cdot f_{1}(1)&{\text{ if }}{\mathsf {S}}=\forall \\f_{1}(0)*f_{1}(1)&{\text{ if }}{\mathsf {S}}=\exists .\\(1-r)f_{1}(0)+rf_{1}(1)&{\text{ if }}{\mathsf {S}}=\mathrm {R} .\end{cases}}}$

إذا فشل أي منهما، فارفض.

• المرحلة الأولى : P → V : P يرسل${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},z)}$كدالة متعددة الحدود في z . r ₁ تشير إلى القيم العشوائية المحددة مسبقًا لـ${\displaystyle r_{1},\dots ,r_{i-1}}$

يستخدم V المعاملات لتقييم${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},0)}$و${\displaystyle f_{i}(r_{1},\dots ,r_{i-1},1)}$ثم يتحقق من أن درجة متعددة الحدود لا تتجاوز n وأن المتطابقات التالية صحيحة:

${\displaystyle f_{i-1}(r_{1},\dots ,r_{i-1})={\begin{cases}f_{i}(r_{1},\dots ,r_{i-1},0)\cdot f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\forall \\f_{i}(r_{1},\dots ,r_{i-1},0)*f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\exists .\end{cases}}}$

${\displaystyle f_{i-1}(r_{1}\dots r)=(1-r)f_{i}(r_{1},\dots ,r_{i-1},0)+rf_{i}(r_{1},\dots ,r_{i-1},1){\text{ if }}{\mathsf {S}}=\mathrm {R} .}$

إذا فشل أي منهما، فارفض.

V → P : يختار V قيمة عشوائية r من F ويرسلها إلى P. (إذا${\displaystyle {\mathsf {S}}=\mathrm {R} }$ثم يحل هذا r محل r السابق ).

انتقل إلى المرحلة i  +  1 حيث يجب على P إقناع V بأن${\displaystyle f_{i}(r_{1},\dots ,r)}$هذا صحيح.

• المرحلة k + 1 : تقييم V${\displaystyle p(r_{1},\dots ,r_{m})}$ثم يتحقق مما إذا${\displaystyle p(r_{1},\dots ,r_{m})=f_{k}(r_{1},\dots ,r_{m})}$إذا كانت متساوية فإن V تقبل، وإلا فإن V ترفض.

هذا هو نهاية وصف البروتوكول.

إذا كانت ψ صحيحة، فإن V سيقبل عندما يتبع P البروتوكول. وبالمثل إذا${\displaystyle {\tilde {P}}}$هو مُثبت خبيث يكذب، وإذا كانت ψ خاطئة، فإن${\displaystyle {\tilde {P}}}$سيتعين أن يكون في المرحلة 0 ويرسل قيمة ما لـ f _0. إذا كان في المرحلة i ، فإن V له قيمة غير صحيحة لـ${\displaystyle f_{i-1}(r_{1},\dots )}$ثم${\displaystyle f_{i}(r_{1},\dots ,0)}$و${\displaystyle f_{i}(r_{1},\dots ,1)}$من المرجح أن يكون هذا غير صحيح أيضًا، وهكذا دواليك. احتمال${\displaystyle {\tilde {P}}}$إن الحصول على نتيجة عشوائية لـ r هو على الأكثر درجة متعددة الحدود مقسومة على حجم الحقل:${\displaystyle n/n^{4}}$يتم تنفيذ البروتوكول عبر O ( n² ⁾ مرحلة، لذا فإن احتمال ذلك${\displaystyle {\tilde {P}}}$إذا حالف الحظ في مرحلة ما، فإن احتمالية حدوث ذلك تكون ≤ 1/ n .${\displaystyle {\tilde {P}}}$إذا لم يكن الأمر محظوظًا أبدًا، فسوف يتم رفض V عند المرحلة k +1.

بما أننا أثبتنا الآن أن كلاً من IP ⊆ PSPACE و PSPACE ⊆ IP ، نستنتج أن IP = PSPACE كما هو مطلوب. علاوة على ذلك، أثبتنا أنه يمكن اعتبار أي خوارزمية IP خوارزمية عامة، لأن عملية الاختزال من PSPACE إلى IP تتمتع بهذه الخاصية.