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

إذا برهنا أن 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، ISBN 978-0-521-42426-4، مؤرشف من الأصل في 07 فبراير 2015

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