مرجع
آخر الزيارات

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

175 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في نظرية التعقيد الحسابي البرهنة بالحشو هي وسيلة مشروطة للبرهنة وهو إذا تساوى قسمين (أو اختلفا) فكذلك كذلك الأقسام الكبيرة كذلك. تتناول المقالة 3 أقسام، منها «فلتكن L∈NEXP»، «نلاحظ ان 'L تتبع القسم NP ,» و«امثلة».
المحتويات
  1. فلتكن L∈NEXP
  2. نلاحظ ان 'L تتبع القسم NP ,
  3. امثلة

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

فلتكن 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 وهذا باستخدام البرهنة بالحشو كالتالي:

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.