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

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

امثلة

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

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

فلتكن L∈NEXP

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

فلتكن 'L اللغة التالية : ${\displaystyle 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 الآن تتبع القسم الاصغر نتيجة الحشو ما معناه :

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

مصادر

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, مطبعة جامعة كامبريدج, صفحة 57,  , مؤرشف من الأصل في 07 فبراير 2015

موسوعات ذات صلة :

• موسوعة علم الحاسوب