مسألة كثيرة حدود غير قطعية كاملة

مسألة NP كاملة
	قابلية الإرضاء 3سات; NAE; أو آي تي; ;
	تلوين مخطط تلوين مخطط بثلاثة ألوان; تلوين مخطط مستو بثلاثة ألوان; ;
	زمرة كبرى
	مسار هاملتونياني
	عدل

معلومات عامة
صنف فرعي من	مسألة حوسبية
جزء من	مسائل NP صعبة; كثير حدود غير قطعي
جانب من جوانب	مسألة P=NP
ممثلة بـ	completeness (en)
لديه جزء أو أجزاء	weak NP-completeness (en) ; strong NP-completeness (en)

في الرياضيات صنف التعقيد، تعرف المسائل كثيرة الحدود غير القطعية الكاملة (NP-complete problems)، بأنها كل ما يحقق الشرطين الآتيين:

لكل لغة،L, موجودة في NP يوجد دالة $f:\Sigma ^{*}\rightarrow \Sigma ^{*}$ بحيث ان عدد الحسابات التي تقوم بها هو دالة متعددة الحدود بالنسبة لمدخلها، بحيث ان f :

إذا $f(x)\in A\iff x\in L$ وإذا $f(x)\notin A\iff x\notin L$

المسألة A من صنف NP أي يمكن بناء آلة تورنغ غير حتمية تقرر اللغة A.

أول لغة عرفت بانها NP كاملة هي SAT حيث قام كل من كوك وليفين باثبات هذا كل على حدا، ومنذ ذلك الحين كثير من المسائل عُرف انها NP كاملة.

أصول التسمية

في عام 1973 بادر دونالد كانوث في البحث عن مصطلح يصف أصعب المشاكل في NP. فقام باقتراع لدى الاختصاصيين.^[1] حصل على العديد من المقترحات البعض منها مبتكرة للغاية. وجاء الحل الفائز من مجموعة في مختبرات بل (ربما كان فيها ديفيد جونسون)، كما هو معروف: NP-صعب و NP-كامل.

يقول كانوث في النهاية: «المشاكل NP-صعبة تمس الكثير من الناس، وهذا هو السبب الذي جعلني أبحث عن مصطلح خاص يستخدم لدى الجميع. قول أن مشكل NP-صعب يقل تقنية لكنه ليس سيئ لغاية أن لا يكون صالحا للاستعمال.NP ، NP، P-صعب، أو NP-كامل، ما هي إلا عبارات جد تقنية تعزل الاختصاصيين وتدهش الآخرين.»

و يقدم جونسون توضيحات رفيعة المصداقية (صفحة 119 للكتاب^[2] وكذلك في المرجع^[3]) عن الدوافع الفعلية لكانوث وهي عندما بدأ تأليف المجلد الرابع لكتابه الذائع الصيت «فن برمجة الحاسوب» إبان ظهور نظرية التعقيد الحسابي غداة عمل ستيفن كوك^[4] ثم ريتشارد كارب^[5] ، لقد سئم من تكرار نفس الجملة الطويلة التي كانت تعرّف هذه الفئة من الخوارزميات قبل هذا. فأوقف كل شيء وأطلق دعوته لمصطلح مستحدث مرفقة بثلاثة اقتراحات رفضها الخبراء تلقائيا.

اللغة SAT

اولا نعرف ما هي الصيغ البوليانية: وهي معادلة فيها كل متغير يمكن ان يحصل على قيمتين 0 أو 1 , وعادة ما يستخدم النفي ( $\lnot$ ), العطف ( $\land$ ) أو الفصل ( $\lor$ )في الصيغة وتسمى هذه الصيغة CNF إذا كانت مركبة من عدة صيغ ثانوية بحيث ان كل صيغة كهذه هي فصل ( $\lor$ ) عدة متغيرات والصيغة الاساسية هي عطف ( $\land$ )الصيغ الثانوية.

واللغة SAT هي: معطى صيغة CNF , $\phi$ , هل يوجد قيم للمتغيرات بحيث ان الصيغة المعطاة قيمتها 1 ؟

مثال: لنفرض معطى: $\phi =(x_{1}\lor x_{2})\land (\lnot x_{1}\lor x_{2}\lor x_{3})\land (\lnot x_{2})$ إذا عوضنا القيم التالية: $x_{1}=1,x_{2}=0,x_{3}=1$ الصيغة المعطاة تكون قيمها 1

مبرهنة كوك وليفين

نص المبرهنة هو: SAT مشكل حدودي غير محدد كامل (NP-complete).

تنسب في الأغلب لكوك، حيث أن ليفين وجد نفس النتائج دون أن يكون على علم بنتائج كوك، ففي ذلك الوقت لم تكن هناك وسائل اتصال متطورة (ما بين 1971 و 1974).

لائحة ب 21 مسألة NP كلاسيكية (كارب)

المسائل الكلاسيكية

SATISFIABILITY : الاكتفاء، إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف، صحيحة.
CLIQUE : الزمرة، إيجاد زمرة أي مخطط (graph) كامل ذو بعد محدد ضمن مخطط آخر.
SET PACKING :
VERTEX COVER : إيجاد ضمن مخطط مجموعة ارتباطات تتصل بكل القمم.
SET COVERING :
FEEDBACK ARC SET :
FEEDBACK NODE SET :
DIRECTED HAMILTONIAN CIRCUIT : البحث عن مسار هاملتونياني مغلق
UNDIRECTED HAMILTONIAN CIRCUIT : البحث عن مسار هاملتونياني مفتوح
0-1 INTEGER PROGRAMMING :
3-SAT : إيجاد قيم لمتغيرات ثنائية تجعل الصيغة العادية لعطف صحيحة تضم كل مجموعة 3 عناصر.
CHROMATIC NUMBER : تحديد أصغر عدد تلوين مخطط حيث كل قمتين مرتبطتين يكون لهما لونان مختلفان.
CLIQUE COVER :
EXACT COVER :
MATCHING à 3 dimensions :
STEINER TREE :
HITTING SET :
KNAPSACK :
JOB SEQUENCING :
PARTITION :
MAX-CUT :

المفهوم النظري المتوقع لحل مسألة كثيرة حدود غير قطعية كاملة

إذا تمكن شخص من حل مسألة واحد NP-complete بوقت حدودي فهذا يعني انه يستطيع حل كل مسألة في NP , وقد تم برهنة التالي في حال حدوث امر مشابه:

${\mbox{ NP=P}}$ وهذا بشكل مباشر نابع من صفة الاختصار عند مسألة NP كاملة أي بما ان كل مسألة في NP يمكن اختصارها لهذه المسألة التي تتبع P حسب الفرضية أن المسائل الكاملة يمكن حلها بوقت حدودي حينها وبما ان الاختصار أيضا كثير حدود حينها نستطيع محاكاة الاختصار وايضا الآلة التي تحل المسألة الكاملة بوقت كثير الحدود لذا فانه كل مسألة في NP تتبع أيضا P .
${\mbox{EXP = NEXP}}$ وهذا نابع من علة التبطين. أي أن EXP صفاتها مشابهة لصفات P ولكن المقاييس يجب ان تكون أكبر.
${\mbox{PH=NP}}$ وهذا يعتد به العلماء على ان حل مسائل NP كاملة غير ممكن، وذلك للاعتقاد ذي الدلائل ان PH وهو هرم مسائل كثيرة الحدود، انه لا يمكن ان ينهار لاي صنف ذي درجة نهائية.
لا يوجد دالة تشفير ذات اتجاه واحد (one way function) وهي دوال يسهل حسابها ولكن من الصعب حساب مقلوبها وهي تعتمد بشكل كبير على مسائل NP , ووجودها غير مؤكد حتى وان $NP\neq P$

هناك اثار أخرى منها ما يجعل العالم مكانا مثاليا والتطور التكنولوجي سوف يتضاعف خلال فترة هي قصيرة جدا، كما لحل هذه المسائل الكثير من التأثير في علم الحاسوب بكل فروعه والبيولوجيا والرياضيات.

حل مسائل كاملة كثيرة حدود غير قطعية هو مسألة مفتوحة وغير معلوم القدرة على حل مسائل كهذه أو عدمها، وقد عُرِض مليون دولار لمن يحل المسألة NP≠P والتي بعبارات أخرى هل يمكن حل مسائل NP كاملة بوقت حدودي؟ والذي يحل هذه المسألة يعني يأتي بخوارزمية تفعل هذا فانه يحصل ليس فقط على مليون ولكن ستة ملايين وذلك لانه يمكن حل المسائل الأخرى بواسطة هذه المسألة إذا كانت الإجابة أنَّ NP=P .

مراجع

^ KNUTH, Donald E. A terminological proposal. ACM SIGACT News, vol. 6, no 1, p. 12-18, 1974. نسخة محفوظة 2 ديسمبر 2018 على موقع واي باك مشين.
^ Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979
^ JOHNSON, David S. A brief history of NP-completeness, 1954–2012. D ocumenta Mathematica, p. 359-376, 2012. نسخة محفوظة 17 ديسمبر 2019 على موقع واي باك مشين.
^ S. Cook. The complexity of theorem proving procedures. In Proc. 3rd Ann. ACM Symp. on Theory of Computing, pages 151–158, 1971. نسخة محفوظة 4 يوليو 2017 على موقع واي باك مشين.
^ R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pages 85–103, New York, . Plenum Press.1972 نسخة محفوظة 21 نوفمبر 2018 على موقع واي باك مشين.

انظر أيضا

[1] KNUTH, Donald E. A terminological proposal. ACM SIGACT News, vol. 6, no 1, p. 12-18, 1974. نسخة محفوظة 2 ديسمبر 2018 على موقع واي باك مشين.

[2] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979

[3] JOHNSON, David S. A brief history of NP-completeness, 1954–2012. D ocumenta Mathematica, p. 359-376, 2012. نسخة محفوظة 17 ديسمبر 2019 على موقع واي باك مشين.

[4] S. Cook. The complexity of theorem proving procedures. In Proc. 3rd Ann. ACM Symp. on Theory of Computing, pages 151–158, 1971. نسخة محفوظة 4 يوليو 2017 على موقع واي باك مشين.

[5] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pages 85–103, New York, . Plenum Press.1972 نسخة محفوظة 21 نوفمبر 2018 على موقع واي باك مشين.

[1]

[2]

[3]

[4]

[5]