شهادة (التعقيد)

في نظرية التعقيد الحسابي ، تُعرَّف الشهادة (وتُسمى أيضًا الشاهد ) بأنها سلسلة نصية تُثبت صحة إجابة عملية حسابية ، أو تُثبت انتماء سلسلة نصية معينة إلى لغة ما . غالبًا ما يُنظر إلى الشهادة على أنها مسار حل ضمن عملية التحقق، والتي تُستخدم للتحقق مما إذا كانت إجابة المسألة "نعم" أم "لا".

في نموذج شجرة القرار الحسابي، يمثل تعقيد الشهادة الحد الأدنى لعدد${\displaystyle n}$يجب تعيين قيمة لمتغيرات الإدخال في شجرة القرار لتحديد قيمة الدالة المنطقية بشكل قاطع.${\displaystyle f}$.

يُستخدم مفهوم الشهادة لتعريف شبه قابلية الحسم : ^{[ 1 ]} لغة رسمية${\displaystyle L}$تكون شبه قابلة للتقرير إذا كانت هناك علاقة مسند ثنائية الموضع${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$بحيث${\displaystyle R}$قابلة للحساب ، بحيث يكون لكل${\displaystyle x\in \Sigma ^{*}}$:

 إذا كان x ∈ L ⇔ يوجد y بحيث يكون R(x, y)

في هذا التعريف، يمثل y الشهادة أو الشاهد على عضوية x في L.

تُقدّم الشهادات أيضًا تعريفات لبعض فئات التعقيد التي يمكن وصفها، بدلاً من ذلك، من حيث آلات تورينغ غير الحتمية . لغة${\displaystyle L}$تكون في فئة NP إذا وفقط إذا وُجدت متعددة حدود${\displaystyle p}$وآلة تورينج محدودة الوقت متعدد الحدود${\displaystyle M}$بحيث كل كلمة${\displaystyle x\in \Sigma ^{*}}$مكتوبة باللغة${\displaystyle L}$تحديداً إذا كانت هناك شهادة${\displaystyle c}$بطول لا يتجاوز${\displaystyle p(|x|)}$بحيث${\displaystyle M}$يقبل الزوج${\displaystyle (x,c)}$[ ^{2 ]} فئة co-NP لها تعريف مشابه، باستثناء وجود شهادات للكلمات غير الموجودة ^في اللغة.

تحتوي فئة NL على تعريف للشهادة: أي مسألة في هذه اللغة لها شهادة ذات طول متعدد الحدود، يمكن التحقق منها بواسطة آلة تورينغ حتمية محدودة المساحة اللوغاريتمية، قادرة على قراءة كل بت من الشهادة مرة واحدة فقط. ^{[ 3 ]} بدلاً من ذلك، يمكن استبدال آلة تورينغ الحتمية محدودة المساحة اللوغاريتمية المذكورة أعلاه بآلة تورينغ احتمالية محدودة الخطأ ذات مساحة ثابتة، يُسمح لها باستخدام عدد ثابت فقط من البتات العشوائية. ^{[ 4 ]}

مشكلة تحديد، بالنسبة لرسم بياني معين${\displaystyle G}$والرقم${\displaystyle k}$إذا كان الرسم البياني يحتوي على مجموعة مستقلة بحجم${\displaystyle k}$ينتمي إلى فئة NP . بالنظر إلى زوج${\displaystyle (G,k)}$في اللغة، الشهادة عبارة عن مجموعة من${\displaystyle k}$الرؤوس التي لا تكون متجاورة مثنى مثنى (وبالتالي تشكل مجموعة مستقلة من الحجم${\displaystyle k}$). ^{[ 5 ]}

أما المثال الأكثر عمومية، فيما يتعلق بمشكلة تحديد ما إذا كانت آلة تورينج معينة تقبل مدخلات في عدد معين من الخطوات، فهو كما يلي:

L = {<<M>, x, w> | هل يقبل <M> قيمة x في |w| خطوة؟} أثبت أن L ∈ NP. المُدقِّق: يحصل على السلسلة c = <M>، x، w بحيث |c| <= P(|w|) تحقق مما إذا كانت c عملية حسابية مقبولة لـ M على x بعدد خطوات لا يتجاوز |w| |c| <= O(|w| 3 ) إذا كان لدينا حساب لآلة تورينج مكون من k خطوة، فإن الحجم الإجمالي لسلسلة الحساب هو k² . بالتالي، إذا كان <<M>, x, w> ∈ L، فإنه يوجد c ≤ a|w| ³ بحيث يكون <<M>, x, w, c> ∈ V ∈ P

• الشاهد (في الرياضيات) ، مفهوم مماثل في المنطق الرياضي

• بورمان، هاري؛ دي وولف، رونالد (2002)، مقاييس التعقيد وتعقيد شجرة القرار: دراسة استقصائية.
• التعقيد الحسابي: منهج حديث، بقلم سانجيف أرورا وبواز باراك