البرهنة بالحشو

في نظرية التعقيد الحسابي البرهنة بالحشو هي وسيلة مشروطة للبرهنة وهو إذا تساوى قسمين (أو اختلفا) فكذلك أيضا الأقسام الكبيرة كذلك.

امثلة

إذا برهنا أن NP=P حينئذ EXP=NEXP وهذا باستخدام البرهنة بالحشو كالتالي:

لنفرض أن: NP=P , ونريد أن نبرهن: EXP=NEXP , يكفي ان نبرهن أن NEXP⊆EXP وذلك ان الاحتواء العكسي مفهوم ضمنا.

فلتكن L∈NEXP

بما أن L تابعة للقسم NEXP لذا يوجد الة تورنغ غير قطعية M التي تقرر L بوقت $2^{n^{c}}$ ,

فلتكن 'L اللغة التالية: $L'=\{x1^{2^{|x|^{c}}}|x\in L\}$

نلاحظ ان 'L تتبع القسم NP ,

وذلك لانه باعطائنا مدخل 'x ذو الهيئة x'=x1^2|x|c يمكننا ان نقرر بوقت كثير الحدود بواسطة الآلة M إذا ما يتبع 'L .

وبما اننا فرضنا ان NP=P حينها يوجد آلة حتمية التي تقرر 'L نرمز لها 'M .

حينها نبرهن ان L تتبع EXP بالشكل التالي:

باعطائنا x حاكي عمل 'M على المدخل x'=x1^2|x|c وافعل مثلما تفعل الآلة.

معنى الحشو في المثل الاخير: أننا «حشونا» المدخل بكثير من ال 1 بحيث أن اللغة L الآن تتبع القسم الاصغر نتيجة الحشو ما معناه:

لنفرض ان طول المدخل: $|x|=n$ , وبعد الحشو: $|x'|=2^{|x|^{c}}$ .

مصادر

• Arora، Sanjeev؛ Barak، Boaz (2009)، Computational Complexity: A Modern Approach، مطبعة جامعة كامبريدج، ص. 57، ISBN:978-0-521-42426-4، مؤرشف من الأصل في 2015-02-07