هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها

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

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث


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

امثلة

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

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

فلتكن L∈NEXP

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

فلتكن 'L اللغة التالية: L={x12|x|c|xL}

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

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

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

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

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

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

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

مصادر

  1. ^ "معلومات عن البرهنة بالحشو على موقع xlinux.nist.gov". xlinux.nist.gov. مؤرشف من الأصل في 2022-02-14.