كثير حدود غير قطعي
المحتويات

على سبيل التعريف، في نظرية التعقيد الحسابي، يعدّ الصنف كثير الحدود غير الحتمي (nondeterministic polynomial time) فئة تعقيد تُستعمل لتصنيف . تمثل NP مجموعة مسائل القرار التي تمتلك الحالات التي تكون إجاباتها "نعم" براهين يمكن التحقق منها في زمن كثير الحدود بواسطة آلة تورنغ حتمية، أو على نحو مكافئ، هي مجموعة المسائل التي يمكن حلها في وقت حدودي بواسطة آلة تورنغ غير حتمية. ونتناول فيما يلي مزيدًا من التفاصيل.
من جانب آخر، التعريف الأول هو أصل تسمية هذا الصنف (الزمن كثير الحدود غير الحتمي). ويُعدّ التعريفان متكافئين، نظرًا لأن خوارزمية آلة تورينغ غير الحتمية تتكوّن من مرحلتين: المرحلة الأولى تتعلق بتخمين حلٍّ للمسألة، ويتم هذا التخمين بصورة غير حتمية. أما المرحلة الثانية فتتعلق بالتحقق من صحة هذا التخمين، ويتم ذلك بصورة حتمية.
علاوةً على ذلك، الصنف كثير الحدود غير الحتمي هو مجموعة مسائل القرار التي يمكن التحقق منها في وقت حدودي عبر آلة تورينغ حتمية.
علاوةً على ذلك، الصنف كثير الحدود غير الحتمي هو مجموعة مسائل القرار التي يمكن حلها في وقت حدودي عبر آلة تورينغ غير حتمية.
اللغة في NP
وفي السياق ذاته، على وجه التقريب كل المسائل العملية موجودة في هذا القسم ولكن في حال ان حينها لا يوجد لاي من هذه المسائل خوارزمية جيدة بمعنى انه لا توجد آلة تيورنج حتمية بوقت حدودي تقرر هذه اللغات.
يمكن اختصار أو تحويل (reduction) كل لغة في NP إلى هذه اللغة
تعريف
وهذا التعريف هو أول تعريف ل-NP.
يوجد عدة تعريفات ل-NP ولعل اهمها هو التالي:
كذلك، لغة متواجدة في NP إذا كان هناك متعدد حدود وآلة تيورنج متعددة الحدود M (أي ان عدد حسابات M هو دالة متعددة الحدود بطول المدخل أي انه يوجد متعدد حدود حيث ان كمية حسابات (M(x هو (|g(|x عندما x يعبر عن المدخل للالة M و-|x| هو طول المدخل) حيث انه لكل :
علاوةً على ذلك، في بداية التسعينات برهنت هذه النظرية لتفتح افق جديدة في علوم الحاسوب ونظرية PCP هي نظرية اساسية في علم التعقيد إذ انه بواسطة هذا التعريف باتت صورة المسائل التي هي NP كاملة التي يمكن اعطائها حل مقرب اوضح حيث نتج عن هذه النظرية الكثير من النتائج عن صعوبة تقريب حل مسائل NP كاملة.
في هذا الإطار، تعريف NTIME: لكل دالة و- بحيث ان إذا يوجد ثابت c>0 وأيضا يوجد NDTM cT(n)-time (آلة تيورنج غير حتمية) M بحيث: .
كذلك، نعرف اولا زمن حساب لالة غير حتمية ثم نعرف NP ليكون كل لغة يمكن تقريرها بآلة تيورنج غير حتمية بحيث ان زمن حسابها متعدد الحدود،
من جهة ثانية، إذا كان و بحيث ان 1=(M(x,u حينها نسمي u اثبات أو برهان(certificate) ل-x ونسمي M آلة فاحصة(verifier)(لانها تفحص إذا كان x في L بواسطة برهان u).
حينها نعرف NP بالشكل التالي:
إذا عندما: حينها NP=P
- إذا حينها NP=P أو بشكل عام إذا أي لغة في قسم NP كامل موجودة في P حينها NP=P
- ملاحظات
- مراجع
- انظر كذلك
تاريخ
كذلك، في بداية الستينات من القرن العشرين، حاول العالم Karp حل مسألة التقرير لمسألة البائع المتجول وهذا كان بادئ الامر وبعد وقت قصير Rabin اسس نظرية التعقيد ووضع حجارة الاساس لها وكلمة التعقيد(complexity) ظهرت فقط في سنة 1965 وبعدها تم تعريف متى تكون الخوارزمية «جيدة» وتم هذا بواسطة Edmonds، اما cook فقد عرف NP وP وكذلك عرف مسائل NP كاملة وبين ان SAT هي كذلك واظهر ان كل مسألة NP كاملة يمكن حلها بواسطة SAT وذلك يتم بواسطة دالة تحويل (reduction) وقد عرف Karp لاحقا مسائل NP كاملة منها TSP وعرفت هذه المسائل بقائمة karp ال-21 وفي عام 2000 تم رصد جائزة بمبلغ مليون دولار لمن يحل مسألة NP=P.
القسم RP
من جانب آخر، مسألة تقرير S في RP إذا يوجد خوارزمية احتمالية بوقت حدودي A بحيث ان الاحتمال بأن الخوارزمية A تقرر x بشكل صحيح أكبر من أي: ، ولكل الخوارزمية لا تخطأ في تقرير x أي:
علاوةً على ذلك، RP هو اختصار Randomized Polynomial time وهذا القسم يعتبر من الاقسام العملية وذلك بالرغم من عدم معرفة إذا ما RP=P حيث انه يمكن كتابة برامج احتمالية وهذا يمكننا من استخدام اللغات فيه، أحد أهم اللغات التي فيه والتي لا يعرف لها خوارزمية حتمية بوقت حدودي هي مسألة فحص إذا ما متعددا الحدود متساويين.
امثلة
- مشكلة التفكيك إلى جداء عوامل أولية : ايجاد العوامل الاولية لعدد ما .
- باعطائنا دالتين متعددتي الحدود، فحص هل هما متطابقين .
- نظريات مهمة
ومن جهة أخرى، مشكلة تلوين المخطط : باعطائنا مُخطط هل يمكن تلوينه بثلاثة الوان بحيث أن كل ضلع رأسيها ملونين بالوان مختلفة ؟
هاتان اللغتان هما NP كاملتين كذلك.
في هذا الإطار، مشكلة المخطط الكامل ضمن مخطط : {clique={(,k): G graph and k number , Is there clique of size k وهي لغة كل المخطوطات التي يمكن فيها مخطوط كامل بكبر k?
{p:هل p عدد اولي ؟}=PRIME وهذه اللغة موجودة في P
تصنيفات مهمة داخل NP
من جهة ثانية، لعل أحد أهم التصنيفات في NP هو القسم P وهو قسم اللغات التي يمكن تقريرها بواسطة آلة تيورنج حتمية بوقت حدودي، وهذا القسم يعتبرا مهما لان كل هذه اللغات لها استخدام عملي في علم الحاسوب.
مسائل NP كاملة وهي قسم لغات يتوفر فيها شرطان:
التعريف بواسطة نظرية PCP
من جهة ثانية، في مطلع التسعينيات، أثبتت هذه النظرية (المعروفة بـ نظرية الإثبات القابل للتحقق العشوائي (PCP)) وأفتحت آفاقًا جديدة في علوم الحاسوب. وتُعتبر من النظريات الأساسية في نظرية التعقيد الحسابي، إذ أسهم هذا التعريف في توضيح حدود إمكانية التقريب لمسائل NP-كاملة، وأفضى إلى نتائج جوهرية تتعلق بصعوبة إيجاد حلول مقرَّبة لتلك المسائل.
قسم تعقيد
مسألة P=NP
نظرية التعقيد الحسابي.
تعريف
وعلى صعيد آخر، تقول هذه الصيغة ببساطة: المدخل x ينتمي إلى اللغة L، إذا وُجد برهان u (أي إجابة مقترحة بحجم معقول (كثير الحدود)) تستطيع الفاحصة M التحقق من صحته.
من جهة ثانية، u: برهانًا أو إثباتًا (certificate) لـ x — أي الإجابة التي نتحقق منها،
ومن جهة أخرى، إذا أعطيتَ شخصًا ما إجابةً مقترحة لمسألة ما، فهل يستطيع التحقق من صحتها في وقت معقول (كثير حدود)؟ إذا كانت الإجابة نعم، فالمسألة تنتمي إلى NP.
يكون التعريف الرسمي كالآتي:
إذا كان وكان بحيث أن ، فحينها نسمّي:
من جانب آخر، وهذا هو أول تعريف تاريخي لـ NP، ومنه اشتُقَّت التسمية: الزمن الحدودي غير الحتمي.
التعريف بواسطة الفاحص (Verifier)
لغة متواجدة في NP إذا كان هناك:
ماذا تعني هذه الصيغة؟
- M: آلةً فاحصة (verifier) — أي البرنامج الذي يتحقق من صحة البرهان.
- التعريف بواسطة آلة تورنغ غير حتمية (NDTM)
- نُعرِّف أولًا زمن الحساب لآلة تورنغ غير حتمية، ثم نُعرِّف NP على أساسه.
- تعريف NTIME:
- لكل دالة ولغة ، نقول إن:
- إذا وُجد ثابت ، ووُجدت آلة تورنغ غير حتمية تعمل في زمن ، وتُسمى M، بحيث:
- إذا يُعرَّف الصنف NP على النحو التالي:
وعلى صعيد آخر، يوجد عدة تعريفات للصنف الحدودي غير الحتمي (NP)، وأهمها ما يلي:
بحيث أنه لكل :
متعدد حدود — يحدد الحجم الأقصى المسموح به للبرهان،
وفي هذا الصدد، مثال: في لعبة السودوكو، قد يصعب إيجاد الحل، لكن إذا أعطيتك جدولًا مملوءًا، يمكنك التحقق من صحته بسرعة بمجرد فحص الصفوف والأعمدة والمربعات.
إضافةً إلى ذلك، وآلة تورنغ حتمية متعددة الحدود M — وهي ما نسميه الفاحصة، أي البرنامج الذي يتحقق من صحة الإجابة،
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟