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

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

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

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

فلتكن L∈NEXP

بما أن L تابعة للقسم NEXP لذا يوجد الة تورنغ غير قطعية M التي تقرر L بوقت  ,

فلتكن 'L اللغة التالية: 

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

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

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

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

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

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

لنفرض ان طول المدخل:  , وبعد الحشو:  .

مصادر 

 

نظرية التعقيد الحسابي