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

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أكتوبر 2015)

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

إذا برهنا أن 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، مؤرشف من الأصل في 2015-02-07

هذه بذرة مقالة عن علم الحاسوب النظري بحاجة للتوسيع. فضلًا شارك في تحريرها.