البرهنة بالحشو
في البداية، في نظرية التعقيد الحسابي البرهنة بالحشو هي وسيلة مشروطة للبرهنة وهو إذا تساوى قسمين (أو اختلفا) فكذلك كذلك الأقسام الكبيرة كذلك. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
فلتكن L∈NEXP
فلتكن 'L اللغة التالية:
وعلى صعيد آخر، بما أن L تابعة للقسم NEXP لذا يوجد الة تورنغ غير قطعية M التي تقرر L بوقت ,
نلاحظ ان 'L تتبع القسم NP ,
لنفرض ان طول المدخل: , وبعد الحشو: .
حينها نبرهن ان L تتبع EXP بالشكل التالي:
من جانب آخر، معنى الحشو في المثل الاخير: أننا «حشونا» المدخل بكثير من ال 1 بحيث أن اللغة L الآن تتبع القسم الاصغر نتيجة الحشو ما معناه:
من جهة ثانية، وبما اننا فرضنا ان NP=P حينها يوجد آلة حتمية التي تقرر 'L نرمز لها 'M .
امثلة
وعلى صعيد آخر، لنفرض أن: NP=P , ونريد أن نبرهن: EXP=NEXP , يكفي ان نبرهن أن NEXP⊆EXP وذلك ان الاحتواء العكسي مفهوم ضمنا.
إضافةً إلى ذلك، إذا برهنا أن NP=P حينئذ EXP=NEXP وهذا باستخدام البرهنة بالحشو كالتالي:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟