قائمة مسائل NP-كاملة

هذه قائمة ببعض المسائل الأكثر شيوعًا التي تُصنَّف ضمن فئة NP-complete عند التعبير عنها كمسائل قرار . ونظرًا لوجود آلاف من هذه المسائل المعروفة، فإن هذه القائمة ليست شاملة بأي حال من الأحوال. ويمكن الاطلاع على العديد من المسائل من هذا النوع في كتاب غاري وجونسون (1979) .

الرسوم البيانية والرسوم البيانية الفائقة

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

1-التسطيح ^{[ 1 ]}
المطابقة ثلاثية الأبعاد ^{[ 2 ]}^{[ 3 ]}^{: SP1}
مشكلة عرض النطاق الترددي ^{[ 3 ]}^{: GT40}
البعد الثنائي ^{[ 3 ]}^{: GT18}
شجرة الامتداد الدنيا ذات السعة المحدودة ^{[ 3 ]}^{: ND5}
مسألة فحص المسار (وتُسمى أيضًا مسألة ساعي البريد الصيني ) للرسوم البيانية المختلطة (التي تحتوي على حواف موجهة وغير موجهة). يمكن حل البرنامج في وقت متعدد الحدود إذا كانت جميع حواف الرسم البياني غير موجهة أو جميعها موجهة. ومن بين المتغيرات مسألة ساعي البريد الريفي. ^{[ 3 ]}^{: ND25، ND27}
مسألة تغطية الزمرة ^{[ 2 ]}^{[ 3 ]}^{: GT17}
مشكلة النقر ^{[ 2 ]}^{[ 3 ]}^{: GT19}
التلوين الكامل ، المعروف أيضًا باسم الرقم اللوني ^{[ 3 ]}^{: GT5}
رتبة الدورة
شجرة الامتداد المقيدة بالدرجة ^{[ 3 ]}^{: ND1}
رقم Domatic ^{[ 3 ]}^{: GT3}
مجموعة الهيمنة ، أو ما يُعرف برقم الهيمنة ^{[ 3 ]}^{: GT2}

تشمل الحالات الخاصة من فئة NP-complete مسألة مجموعة الهيمنة على الحواف ، أي مسألة مجموعة الهيمنة في الرسوم البيانية الخطية. وتشمل المتغيرات من فئة NP-complete مسألة مجموعة الهيمنة المتصلة ومسألة الشجرة الممتدة ذات الأوراق القصوى . ^{[ 3 ]}^{: ND2}

مجموعة رؤوس التغذية الراجعة ^{[ 2 ]}^{[ 3 ]}^{: GT7}
مجموعة قوس التغذية الراجعة ^{[ 2 ]}^{[ 3 ]}^{: GT8}
تلوين الرسم البياني ^{[ 2 ]}^{[ 3 ]}^{: GT4}
مسألة تماثل الرسوم البيانية ^{[ 3 ]}^{: GT52}
تُعرف عملية تقسيم الرسوم البيانية إلى رسوم بيانية فرعية من أنواع محددة (مثل المثلثات، والرسوم البيانية الفرعية المتماثلة ، والرسوم البيانية الفرعية الهاميلتونية ، والغابات ، والمطابقات الكاملة ) بأنها مسألة NP-كاملة. وتُعدّ عملية التقسيم إلى زمر مشكلة مماثلة لتلوين مكمل الرسم البياني المُعطى. وتتمثل مشكلة أخرى ذات صلة في إيجاد تقسيم أمثل من حيث عدد الحواف بين الأجزاء. ^[³^]^:^GT11،^GT12،^GT13،^GT14،^GT15،^GT16،^ND14
عدد غروندي للرسم البياني الموجه. ^{[ 3 ]}^{: GT56}
إكمال هاميلتوني ^{[ 3 ]}^{: GT34}
مسألة المسار الهاميلتوني ، الموجهة وغير الموجهة. ^{[ 2 ]}^{[ 3 ]}^{: GT37، GT38، GT39}
مشكلة تماثل الرسم البياني الفرعي المستحث
رقم تقاطع الرسم البياني ^{[ 3 ]}^{: GT59}
مسألة أطول مسار ^{[ 3 ]}^{: ND29}
أقصى رسم بياني ثنائي الأجزاء أو (خاصةً مع الحواف الموزونة) أقصى قطع . ^{[ 2 ]}^{[ 3 ]}^{: GT25، ND16}
مسألة تماثل الرسم البياني الفرعي المشترك الأقصى ^{[ 3 ]}^{: GT49}
أكبر مجموعة مستقلة ^{[ 3 ]}^{: GT20}
أقصى مسار مستحث ^{[ 3 ]}^{: GT23}
أصغر مجموعة مستقلة قصوى، والمعروفة أيضًا باسم أصغر مجموعة مستقلة مهيمنة ^{[ 4 ]}

تشمل الحالات الخاصة الكاملة من نوع NP مشكلة المطابقة الدنيا القصوى ، ^{[ 3 ]}^{: GT10} والتي تساوي بشكل أساسي مشكلة مجموعة الهيمنة على الحافة (انظر أعلاه).

البُعد المتري للرسم البياني ^{[ 3 ]}^{: GT61}
مركز k المتري
الحد الأدنى لدرجة امتداد الشجرة
الحد الأدنى لقطع k
الشجرة الممتدة الدنيا k
اختبار بسيط (التحقق مما إذا كان الرسم البياني المدخل $G$ يحتوي على رسم بياني للإدخال $H$ كجزيء فرعي)؛ وينطبق الشيء نفسه على الجزيئات الفرعية الطوبولوجية
شجرة شتاينر ، أو الشجرة الممتدة الدنيا لمجموعة فرعية من رؤوس الرسم البياني. ^{[ 2 ]} (يمكن حل الشجرة الممتدة الدنيا للرسم البياني بأكمله في وقت متعدد الحدود.)
تعظيم النمطية ^{[ 5 ]}
المثلث أحادي اللون ^{[ 3 ]}^{: GT6}
عرض المسار ، ^{[ 6 ]} أو، بشكل مكافئ، سمك الفاصل الزمني ، وعدد فصل الرؤوس ^{[ 7 ]}
تلوين الرتب
ساعي بريد صيني
أقصر طول إجمالي للمسار في الشجرة الممتدة ^{[ 3 ]}^{: ND3}
اختبار المنحدر رقم اثنين ^{[ 8 ]}
التعرف على الرسوم البيانية للسلاسل ^{[ 9 ]}
مسألة تماثل الرسوم البيانية الفرعية ^{[ 3 ]}^{: GT48}
عرض الشجرة ^{[ 6 ]}
اختبار ما إذا كان من الممكن تمثيل شجرة ما كشجرة امتداد أدنى إقليدية
غطاء الرؤوس ^{[ 2 ]}^{[ 3 ]}^{: GT1}
مشكلة موصل وينر الأدنى

البرمجة الرياضية

مسألة التقسيم الثلاثي ^{[ 3 ]}^{: SP15}
مشكلة تعبئة الصناديق ^{[ 3 ]}^{: SR1}
بائع متجول ذو عنق زجاجة ^{[ 3 ]}^{: ND24}
مشكلة تحديد موقع المنشأة غير المزودة بسعة
مشكلة جدولة تدفق الإنتاج
مشكلة التخصيص المعممة
البرمجة العددية الصحيحة . يُعدّ النوع الذي تُشترط فيه أن تكون قيم المتغيرات إما 0 أو 1، ويُسمى البرمجة الخطية الصفرية-الواحدية، بالإضافة إلى العديد من الأنواع الأخرى، مسائل NP-كاملة ^{[ 2 ]}^{[ 3 ]}^{: MP1}
بعض المشاكل المتعلقة بجدولة ورش العمل
مسألة حقيبة الظهر ، ومسألة حقيبة الظهر التربيعية ، والعديد من المتغيرات ^{[ 2 ]}^{[ 3 ]}^{: MP9}
بعض المشاكل المتعلقة بجدولة المعالجات المتعددة
المطابقة العددية ثلاثية الأبعاد ^{[ 3 ]}^{: SP16}
جدولة المتجر المفتوح
مسألة التقسيم ^{[ 2 ]}^{[ 3 ]}^{: SP12}
مسألة التخصيص التربيعي ^{[ 3 ]}^{: ND43}
البرمجة التربيعية (صعبة من نوع NP في بعض الحالات، وP إذا كانت محدبة)
مسألة مجموع المجموعات الجزئية ^{[ 3 ]}^{: SP13}
تنويعات على مسألة البائع المتجول . تُعدّ المسألة بالنسبة للرسوم البيانية مسألةً كاملةً من فئة NP إذا افترضنا أن أطوال الحواف أعداد صحيحة. أما المسألة بالنسبة للنقاط على المستوى، فهي مسألة كاملة من فئة NP مع المقياس الإقليدي المتقطع والمقياس المستقيم. ومن المعروف أن المسألة صعبة الحل من فئة NP مع المقياس الإقليدي (غير المتقطع). ^{[ 3 ]}^{: ND22، ND23}

اللغات الرسمية ومعالجة السلاسل النصية

أقرب سلسلة ^{[ 10 ]}
مشكلة أطول سلسلة فرعية مشتركة عبر سلاسل متعددة ^{[ 3 ]}^{: SR10}
الصيغة المحدودة لمسألة مراسلة بوست ^{[ 3 ]}^{: SR11}
أقصر تسلسل فائق مشترك عبر تسلسلات متعددة ^{[ 3 ]}^{: SR8}
توسيع لمسألة تصحيح السلسلة إلى سلسلة ^{[ 11 ]}^{[ 3 ]}^{: SR8}

ألعاب وألغاز

حقيبة (حظيرة) ^{[ 12 ]}
سفينة حربية
لعبة Bulls and Cows ، التي تم تسويقها تحت اسم Master Mind : مشاكل تحسين معينة ولكن ليس اللعبة نفسها.
ألغاز مطابقة الحواف
فيلومينو ^{[ 13 ]}
( معمم ) FreeCell ^{[ 14 ]}
جويشي هيروي
هاشيووكاكيرو ^{[ 15 ]}
هياواكي ^{[ 16 ]}
( معمم ) جنون فوري ^{[ 3 ]}^{: GP15}
كاكورو (مجموعات متقاطعة) ^{[ 17 ]}
Kingdomino ^{[ 18 ]}
كوروماسو (المعروف أيضًا باسم كورودوكو) ^{[ 19 ]}
LaserTank ^{[ 20 ]}
الليمنجز (مع حد زمني متعدد الحدود) ^{[ 21 ]}
أضئ ^{[ 22 ]}
لعبة سوليتير ما جونغ (مع النظر إلى البلاطات السفلية)
ماسيو ^{[ 23 ]}
مشكلة اتساق كاسحة الألغام ^{[ 24 ]} (لكن انظر سكوت وستيج وفان رويج ^{[ 25 ]} )
نونوغرام
رقم الهاتف
نوريكابي ^{[ 26 ]}
( الجائحة المعممة ) ^[²⁷^]
لعبة سوليتير بيغ
إكمال الملكات n
الحل الأمثل لمكعب روبيك $N \times N \times N$ ^[²⁸^]
نفس اللعبة
شاكاشاكا
انزلق الرابط على مجموعة متنوعة من الشبكات ^{[ 29 ]}^{[ 30 ]}^{[ 31 ]}
سودوكو ( معمم ) ^[²⁹^]^[³²^]
تاتاميباري
عرض تينتاي
مشاكل متعلقة بلعبة تتريس ^{[ 33 ]}
الحساب اللفظي

آخر

مشكلة تخصيص الأرصفة ^{[ 34 ]}
الوساطة
تجميع كتلة بيتكوين مثالية . ^{[ 35 ]}
مسألة إرضاء العبارات المنطقية (SAT). ^{[ 2 ]}^{[ 3 ]}^{: LO1} توجد العديد من الصيغ المختلفة التي تُصنف أيضًا ضمن مسائل NP-كاملة. ومن أهم هذه الصيغ تلك التي تحتوي فيها كل عبارة على ثلاثة متغيرات حرفية فقط (3SAT)، حيث تُستخدم هذه الصيغة في إثبات العديد من نتائج NP-كاملة الأخرى. ^{[ 3 ]}^{: ص 48}
مشكلة إرضاء الدائرة
استعلام منطقي اقتراني ^{[ 3 ]}^{: SR31}
الترتيب الدوري ^{[ 36 ]}
مسألة التغطية التامة . تبقى مسألة NP-كاملة للمجموعات الثلاثية. قابلة للحل في وقت متعدد الحدود للمجموعات الثنائية (وهي مسألة مطابقة ). ^{[ 2 ]}^{[ 3 ]}^{: SP2}
إيجاد الحل الأدنى العالمي لمسألة هارتري -فوك ^{[ 37 ]}
اختبار التسطح التصاعدي ^{[ 8 ]}
مشكلة المستشفيات والمقيمين فيما يتعلق بالأزواج
جنس العقدة ^{[ 38 ]}
إكمال المربع اللاتيني (مشكلة تحديد ما إذا كان من الممكن إكمال مربع مملوء جزئيًا)
أقصى درجة إرضاء من الدرجة الثانية ^{[ 3 ]}^{: LO5}
مصفوفة الحجم الأقصى - مشكلة اختيار أفضل مجموعة فرعية مُهيأة من مجموعة أكبر $m\times n$ المصفوفة. يرتبط هذا النوع من المسائل بتحليلات QR التي تكشف عن الرتبة والتصميم التجريبي الأمثل D. ^{[ 39 ]}
سلاسل الجمع الدنيا للمتتاليات. ^{[ 40 ]} تعقيد سلاسل الجمع الدنيا للأعداد الفردية غير معروف. ^{[ 41 ]}
المنطق الموجه S5 - قابلية الإرضاء
مشكلة فرز المسافة للفطائر للسلاسل ^{[ 42 ]}
قابلية حل كثيرات الحدود التربيعية ذات المتغيرين على مجموعة الأعداد الصحيحة. ^{[ 43 ]} بالنظر إلى الأعداد الصحيحة الموجبة $\textstyle A,B,C$ تحديد وجود الأعداد الصحيحة الموجبة $x,y$ بحيث $Ax^{2}+By-C=0$
بحسب المقالة نفسها ^{[ 43 ]،} يوجد جذر تربيعي معياري محدود ذو معيار مركب كيفيًا. معطى أعداد صحيحة موجبة $\textstyle A,B,C\geq 0$ ، تحديد وجود عدد صحيح $x\in [0,C]$ بحيث $x^{2}\equiv A{\bmod {B}}$ تبقى المسألة من فئة NP-complete حتى لو تم تحليل العدد إلى عوامل أولية . $B$ يتم توفيرها.
قابلية تسلسل سجلات قواعد البيانات ^{[ 3 ]}^{: SR33}
تغطية المجموعة (وتُسمى أيضًا مسألة "التغطية الدنيا"). وهي تُكافئ، عن طريق نقل مصفوفة الوقوع، مسألة مجموعة الضرب. ^{[ 2 ]}^{[ 3 ]}^{: SP5، SP8}
مجموعة التعبئة ^{[ 2 ]}^{[ 3 ]}^{: SP3}
مشكلة تقسيم المجموعات ^{[ 3 ]}^{: SP4}
الجدولة لتقليل وقت الإنجاز المرجح
فرز الكتل ^{[ 44 ]} (الفرز حسب حركات الكتل)
التقريب المتفرق
تنويعات لمسألة شجرة شتاينر ، وتحديدًا مع المقياس الإقليدي المتقطع والمقياس الخطي. من المعروف أن المسألة صعبة الحل (NP-hard) مع المقياس الإقليدي (غير المتقطع). ^{[ 3 ]}^{: ND13}
نموذج إيزينغ ثلاثي الأبعاد ^{[ 45 ]}

انظر أيضاً

ملحوظات

↑ غريغورييف وبودليندر (2007) .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 كارب (1972)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 غاري آند جونسون (1979)
↑ مجموعة الهيمنة المستقلة الدنيا
↑ براندس، أولريك ؛ ديلينغ، دانيال؛ غارتلر، ماركو؛ غوركه، روبرت؛ هوفر، مارتن؛ نيكولوسكي، زوران؛ فاغنر، دوروثيا (2006)، تعظيم النمطية أمر صعب ، arXiv : physics/0608255 ، Bibcode : 2006physics...8255B
1 2 أرنبورغ، كورنيل وبروسكوروفسكي (1987)
^ كاشيوابارا وفوجيساوا (1979) ؛ أوتسوكي وآخرون. (1979) ; لينجور (1981) .
1 2 غارغ، أشيم؛ تاماسيا، روبرتو (1995). "حول التعقيد الحسابي لاختبارات التسطح التصاعدي والمستقيمي". سلسلة محاضرات في علوم الحاسوب . المجلد 894/1995. الصفحات 286-297 . doi : 10.1007/3-540-58950-3_384 . ISBN 978-3-540-58950-1.
↑ شيفر، ماركوس؛ سيدجويك، إريك؛ ستيفانكوفيتش، دانيال (سبتمبر 2003). "التعرف على رسوم بيانية للسلاسل في NP" . مجلة علوم الحاسوب والنظم . 67 (2): 365-380 . doi : 10.1016/S0022-0000(03)00045-X .
↑ لانكتوت، ج. كيفن؛ لي، مينغ؛ ما، بين؛ وانغ، شاوجيو؛ تشانغ، لوكسين (2003)، "تمييز مشاكل اختيار السلاسل"، المعلومات والحوسبة ، 185 (1): 41-55 ، doi : 10.1016/S0890-5401(03)00057-9 ، MR 1994748
↑ فاغنر، روبرت أ. (مايو 1975). "حول تعقيد مسألة تصحيح السلاسل الموسعة" . وقائع الندوة السنوية السابعة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '75 . الصفحات 218-223 . doi : 10.1145/800116.803771 . ISBN 9781450374194. S2CID 18705107 .
↑ فريدمان، إريك. "ألغاز الحظيرة هي مسائل NP-كاملة" (ملف PDF) . تم الاطلاع عليه بتاريخ 17 أغسطس 2021 .
↑ ياتو، تاكاوكي (2003). تعقيد واكتمال إيجاد حل آخر وتطبيقه على الألغاز . CiteSeerX 10.1.1.103.8380 .
↑ مالتي هيلمرت، نتائج التعقيد لمجالات القياس المعيارية في التخطيط، الذكاء الاصطناعي 143(2):219-262، 2003.
↑ "هاشيووكاكيرو مكتملة من حيث القدرة على استخدام القدرات الخارقة" . مؤرشفة من الأصل في 2 يوليو 2016. تم الاطلاع عليها في 2 يونيو 2015 .
↑ هولزر ورويب (2007)
↑ تاكاهيرو، سيتا (5 فبراير 2002). "تعقيدات الألغاز، ومسائل الجمع المتقاطع، ومسائل الحلول البديلة لها (ASP)" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 7 أكتوبر 2022. تم الاطلاع عليه في 18 نوفمبر 2018 .
↑ نغوين، فييت-ها؛ بيرو، كيفن؛ فاليه، ماثيو (24 يونيو 2020). "اكتمال لعبة Kingdomino™ من فئة NP" . علوم الحاسوب النظرية . 822 : 23-35 . doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975 . S2CID 218552723 .
↑ كولكر، جوناس (2012). "كورودوكو مسألة كاملة من فئة NP" (ملف PDF) . مجلة معالجة المعلومات . 20 (3): 694-706 . doi : 10.2197/ipsjjip.20.694 . S2CID 46486962. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 12 فبراير 2020.
↑ ألكسندرسون، بير؛ ريستاد، بيتر (2020). "LaserTank هي مسألة NP-كاملة". الجوانب الرياضية لعلوم الحاسوب والمعلومات . سلسلة محاضرات في علوم الحاسوب. المجلد 11989. دار نشر سبرينغر الدولية. الصفحات 333-338 . arXiv : 1908.05966 . doi : 10.1007/978-3-030-43120-4_26 . ISBN 978-3-030-43119-8. S2CID 201058355 .
↑ كورمود، غراهام (2004). صعوبة لعبة الليمينغ، أو يا إلهي، المزيد من براهين اكتمال NP (PDF) .
↑ الإضاءة مكتملة NP
↑ فريدمان، إريك. "ألغاز اللؤلؤ هي NP-كاملة" .
↑ كاي (2000)
↑ آلان سكوت، أولريك ستيج، إيريس فان روي، قد لا تكون لعبة كاسحة الألغام NP-كاملة ولكنها صعبة مع ذلك، The Mathematical Intelligencer 33 :4 (2011)، ص 5-17.
↑ هولزر، ماركوس؛ كلاين، أندرياس؛ كوتريب، مارتن؛ روب، أوليفر (2011). "التعقيد الحسابي لـ NURIKABE". Fundamenta Informaticae . 110 ( 1-4 ): 159-174 . doi : 10.3233/FI-2011-534 .
^ ناكاي، كينشيرو. تاكيناجا ياسوهيكو (2012). "NP-اكتمال الوباء" . مجلة معالجة المعلومات . 20 (3): 723-726 . دوى : 10.2197/ipsjjip.20.723 . ردمك 1882-6652 .
↑ ديمين، إريك؛ آيزنستات، سارة؛ رودوي، ميخائيل (2018). حل مكعب روبيك الأمثل هو مسألة NP-كاملة . الندوة الخامسة والثلاثون حول الجوانب النظرية لعلوم الحاسوب (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .
1 2 ساتو، تاكايوكي؛ سيتا، تاكاهيرو (1987). تعقيد واكتمال إيجاد حل آخر وتطبيقه على الألغاز (ملف PDF) . الندوة الدولية حول الخوارزميات (SIGAL 1987). مؤرشف من الأصل (ملف PDF) في 3 مارس 2020. تم الاطلاع عليه في 8 أبريل 2017 .
↑ نوكوي؛ أويجيما (مارس 2007). "اكتمال لغز Slither Link على عدة شبكات باستخدام ASP" . ملاحظات Ipsj Sig . 2007 (23): 129– 136.
↑ كولكر، جوناس (2012). "متغيرات مختارة من روابط الانزلاق هي مسائل NP-كاملة" . مجلة معالجة المعلومات . 20 (3): 709-712 . doi : 10.2197/ipsjjip.20.709 .
↑ دراسة استقصائية لألغاز NP-الكاملة، القسم 23؛ غراهام كيندال، أندرو باركس، كريستيان سبورر؛ مارس 2008. (icga2008.pdf) مؤرشف في 19 يونيو 2022 في Wayback Machine
↑ ديمين، إريك د.؛ هوهنبرغر، سوزان؛ ليبن-نويل، ديفيد (25-28 يوليو 2003). لعبة تتريس صعبة، حتى التقريب منها (ملف PDF) . وقائع المؤتمر الدولي التاسع للحوسبة والتوافقية (COCOON 2003) . بيغ سكاي، مونتانا.
↑ ليم، أندرو (1998)، "مشكلة تخطيط الرصيف"، رسائل بحوث العمليات ، 22 ( 2-3 ): 105-110 ، doi : 10.1016/S0167-6377(98)00010-8 ، MR 1653377
↑ ج. بونو، "تعدين البيتكوين صعب من نوع NP"
↑ جاليل، تسفي؛ مجدو، نمرود (أكتوبر 1977). "الترتيب الدوري مسألة كاملة من فئة NP" . علوم الحاسوب النظرية . 5 (2): 179-182 . doi : 10.1016/0304-3975(77)90005-6 .
↑ ويتفيلد، جيمس دانيال؛ لوف، بيتر جون؛ أسبورو-جوزيك، آلان (2013). "التعقيد الحسابي في البنية الإلكترونية" . فيزياء كيميائية. كيمياء فيزيائية . 15 (2): 397-411 . arXiv : 1208.3334 . Bibcode : 2013PCCP...15..397W . doi : 10.1039/C2CP42695A . PMID: 23172634. S2CID : 12351374 .
↑ أغول، إيان ؛ هاس، جويل ؛ ثورستون، ويليام (19 مايو 2002). "جنس العقدة ثلاثية الأبعاد هو مسألة NP-كاملة" . وقائع الندوة السنوية الرابعة والثلاثين لجمعية ACM حول نظرية الحوسبة . STOC '02. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 761-766 . arXiv : math/0205057 . doi : 10.1145/509907.510016 . ISBN 978-1-58113-495-7. S2CID 10401375 .
↑ Çivril, Ali; Magdon-Ismail, Malik (2009), “حول اختيار مصفوفة فرعية ذات حجم أقصى من مصفوفة والمشاكل ذات الصلة” (ملف PDF) ، علوم الحاسوب النظرية ، 410 ( 47-49 ): 4801-4811 ، doi : 10.1016/j.tcs.2009.06.018 ، MR 2583677 ، مؤرشف من الأصل (ملف PDF) في 3 فبراير 2015
↑ بيتر داوني، وبنتون ليونغ، ورافي سيثي. "حساب المتتاليات باستخدام سلاسل الجمع" مجلة SIAM للحوسبة، 10(3)، 638-646، 1981
↑ دي جيه بيرنشتاين، "خوارزمية بيبينجر للأس" (مسودة)
↑ هيركنز، سي.؛ إيرسيل، إل. في.؛ كيسبر، ج.؛ كيلك، إس.؛ ستوجي، إل.؛ ترومب، ج. (2007). "انعكاسات البادئات على السلاسل الثنائية والثلاثية". مجلة SIAM للرياضيات المتقطعة . 21 (3): 592-611 . arXiv : math/0602456 . doi : 10.1137/060664252 .
1 2 ماندرز، كينيث؛ أدلمان، ليونارد (1976). "مسائل القرار الكاملة من فئة NP لكثيرات الحدود التربيعية" . وقائع الندوة السنوية الثامنة لجمعية ACM حول نظرية الحوسبة - STOC '76 . الصفحات 23-29 . doi : 10.1145/800113.803627 . ISBN 9781450374149. S2CID 18885088 .
↑ بين، دبليو دبليو؛ لارمور، إل إل؛ لطيفي، إس؛ سودبورو، آي إتش (1 يناير 2002). "فرز الكتل صعب". وقائع الندوة الدولية حول البنى المتوازية والخوارزميات والشبكات. I-SPAN'02 . الصفحات 307-312 . doi : 10.1109/ISPAN.2002.1004305 . ISBN 978-0-7695-1579-3. S2CID 32222403 .
↑ باري آرثر سيبرا ، "نموذج إيزينغ كامل من النوع NP"، أخبار SIAM، المجلد 33، العدد 6.

مراجع

عام

غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية ( الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 0519066 . OCLC 247570676 . هذا الكتاب كلاسيكي، حيث يطور النظرية، ثم يصنف العديد من مسائل NP-Complete.
كوك، إس. أ. (1971). "تعقيد إجراءات إثبات النظريات". وقائع الندوة السنوية الثالثة لجمعية آلات الحوسبة حول نظرية الحوسبة، جمعية آلات الحوسبة، نيويورك . الصفحات 151-158 . doi : 10.1145/800157.805047 .
كارب، ريتشارد م. (1972). "قابلية الاختزال بين المسائل التوافقية". في: ميلر، ريموند إي.؛ ثاتشر، جيمس و. (محرران). تعقيد الحسابات الحاسوبية . بلينوم. ص 85-103 .
دون، بي إي. "قائمة مشروحة لمسائل مختارة من فئة NP-complete" . COMP202، قسم علوم الحاسوب، جامعة ليفربول . تم الاطلاع عليه بتاريخ 21 يونيو 2008 .
كريسينزي، P .؛ كان، V.؛ هالدورسون، م.؛ كاربينسكي، م . ووجينجر، ج . "خلاصة وافية لمشاكل تحسين NP" . KTH نادا، ستوكهولم . تم الاسترجاع 21 يونيو 2008 .
دالكه، ك. "مسائل NP-كاملة" . مشروع المراجع الرياضية . تم الاسترجاع في 21 يونيو 2008 .

مشاكل محددة

فريدمان، إي (2002). "ألغاز اللؤلؤ هي مسائل NP-كاملة" . جامعة ستيتسون، ديلاند، فلوريدا . تم الاسترجاع في 9 مارس 2026 .
غريغورييف، أ؛ بودليندر، هـ. ل. (2007). "خوارزميات للرسوم البيانية القابلة للتضمين مع عدد قليل من التقاطعات لكل حافة". Algorithmica . 49 ( 1): 1-11 . CiteSeerX 10.1.1.61.3576 . doi : 10.1007/s00453-007-0010-x . MR 2344391. S2CID 8174422 .
هارتونغ، س؛ نيشتيرلين، أ (2012). "صعوبة NP وقابلية معالجة المعاملات الثابتة لتحقيق متواليات الدرجات باستخدام الرسوم البيانية الموجهة غير الدورية". كيف يحسب العالم . سلسلة محاضرات في علوم الحاسوب. المجلد 7318. سبرينغر، برلين، هايدلبرغ. الصفحات 283-292 . CiteSeerX 10.1.1.377.2077 . doi : 10.1007/978-3-642-30870-3_29 . ISBN 978-3-642-30869-7. S2CID 6112925 .
هولزر، ماركوس؛ روب، أوليفر (2007). "مشكلات التصميم الداخلي - تحليل تعقيد لعبة هياواكي" (ملف PDF) . وقائع المؤتمر الدولي الرابع حول متعة الخوارزميات، سلسلة محاضرات في علوم الحاسوب 4475. سبرينغر، برلين/هايدلبرغ. الصفحات 198-212 . doi : 10.1007/978-3-540-72914-3_18 . ISBN 978-3-540-72913-6.
كاي، ريتشارد (2000). "لعبة كاسحة الألغام هي مسألة NP-كاملة". مجلة الذكاء الرياضي . 22 (2): 9-15 . doi : 10.1007/BF03025367 . S2CID 122435790 . تتوفر معلومات إضافية عبر الإنترنت على صفحات لعبة كاسحة الألغام لريتشارد كاي. مؤرشفة بتاريخ 26 يناير 2018 في موقع Wayback Machine .
كاشيوابارا، ت.؛ فوجيساوا، ت. (1979). "اكتمال مسألة إيجاد رسم بياني فاصل ذي عدد زمر أدنى يحتوي على رسم بياني معطى كرسم بياني فرعي". وقائع الندوة الدولية حول الدوائر والأنظمة . ص 657-660 .
أوتسوكي، تاتسو؛ موري، هاجيمو؛ كوه، إرنست س.؛ كاشيوابارا، توشينوبو؛ فوجيساوا، توشيو (1979). "تخصيص البوابات المنطقية أحادية البعد ومخططات الفترات". معاملات IEEE في الدوائر والأنظمة . 26 (9): 675-684 . doi : 10.1109/TCS.1979.1084695 .
لينغاور، توماس (1981). "الحصى السوداء والبيضاء وفصل الرسوم البيانية". مجلة أكتا إنفورماتيكا . 16 (4): 465-475 . doi : 10.1007/BF00264496 . S2CID 19415148 .
أرنبورغ، ستيفان؛ كورنيل، ديريك ج .؛ بروسكوروفسكي، أندريه (1987). "تعقيد إيجاد التضمينات في شجرة من الرتبة k ". مجلة SIAM للأساليب الجبرية والمنفصلة . 8 (2): 277-284 . doi : 10.1137/0608024 .
كورمود، غراهام (2004). "صعوبة لعبة الليمينغ، أو يا إلهي، المزيد من براهين اكتمال NP". وقائع المؤتمر الدولي الثالث حول المرح مع الخوارزميات (FUN 2004) . الصفحات 65-76 .

روابط خارجية

[FOOTNOTEGrigorievBodlaender2007-1] غريغورييف وبودليندر (2007) .

[karp-2] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 كارب (1972)

[gj1979-3] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 غاري آند جونسون (1979)

[4] مجموعة الهيمنة المستقلة الدنيا

[5] براندس، أولريك ؛ ديلينغ، دانيال؛ غارتلر، ماركو؛ غوركه، روبرت؛ هوفر، مارتن؛ نيكولوسكي، زوران؛ فاغنر، دوروثيا (2006)، تعظيم النمطية أمر صعب ، arXiv : physics/0608255 ، Bibcode : 2006physics...8255B

[acp1987-6] 1 2 أرنبورغ، كورنيل وبروسكوروفسكي (1987)

[7] كاشيوابارا وفوجيساوا (1979) ؛ أوتسوكي وآخرون. (1979) ; لينجور (1981) .

[Comp2Planar-8] 1 2 غارغ، أشيم؛ تاماسيا، روبرتو (1995). "حول التعقيد الحسابي لاختبارات التسطح التصاعدي والمستقيمي". سلسلة محاضرات في علوم الحاسوب . المجلد 894/1995. الصفحات 286-297 . doi : 10.1007/3-540-58950-3_384 . ISBN 978-3-540-58950-1.

[9] شيفر، ماركوس؛ سيدجويك، إريك؛ ستيفانكوفيتش، دانيال (سبتمبر 2003). "التعرف على رسوم بيانية للسلاسل في NP" . مجلة علوم الحاسوب والنظم . 67 (2): 365-380 . doi : 10.1016/S0022-0000(03)00045-X .

[10] لانكتوت، ج. كيفن؛ لي، مينغ؛ ما، بين؛ وانغ، شاوجيو؛ تشانغ، لوكسين (2003)، "تمييز مشاكل اختيار السلاسل"، المعلومات والحوسبة ، 185 (1): 41-55 ، doi : 10.1016/S0890-5401(03)00057-9 ، MR 1994748

[11] فاغنر، روبرت أ. (مايو 1975). "حول تعقيد مسألة تصحيح السلاسل الموسعة" . وقائع الندوة السنوية السابعة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '75 . الصفحات 218-223 . doi : 10.1145/800116.803771 . ISBN 9781450374194. S2CID 18705107 .

[12] فريدمان، إريك. "ألغاز الحظيرة هي مسائل NP-كاملة" (ملف PDF) . تم الاطلاع عليه بتاريخ 17 أغسطس 2021 .

[13] ياتو، تاكاوكي (2003). تعقيد واكتمال إيجاد حل آخر وتطبيقه على الألغاز . CiteSeerX 10.1.1.103.8380 .

[14] مالتي هيلمرت، نتائج التعقيد لمجالات القياس المعيارية في التخطيط، الذكاء الاصطناعي 143(2):219-262، 2003.

[15] "هاشيووكاكيرو مكتملة من حيث القدرة على استخدام القدرات الخارقة" . مؤرشفة من الأصل في 2 يوليو 2016. تم الاطلاع عليها في 2 يونيو 2015 .

[Holzer-Ruepp07-16] هولزر ورويب (2007)

[17] تاكاهيرو، سيتا (5 فبراير 2002). "تعقيدات الألغاز، ومسائل الجمع المتقاطع، ومسائل الحلول البديلة لها (ASP)" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 7 أكتوبر 2022. تم الاطلاع عليه في 18 نوفمبر 2018 .

[18] نغوين، فييت-ها؛ بيرو، كيفن؛ فاليه، ماثيو (24 يونيو 2020). "اكتمال لعبة Kingdomino™ من فئة NP" . علوم الحاسوب النظرية . 822 : 23-35 . doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975 . S2CID 218552723 .

[Kölker12b-19] كولكر، جوناس (2012). "كورودوكو مسألة كاملة من فئة NP" (ملف PDF) . مجلة معالجة المعلومات . 20 (3): 694-706 . doi : 10.2197/ipsjjip.20.694 . S2CID 46486962. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 12 فبراير 2020.

[20] ألكسندرسون، بير؛ ريستاد، بيتر (2020). "LaserTank هي مسألة NP-كاملة". الجوانب الرياضية لعلوم الحاسوب والمعلومات . سلسلة محاضرات في علوم الحاسوب. المجلد 11989. دار نشر سبرينغر الدولية. الصفحات 333-338 . arXiv : 1908.05966 . doi : 10.1007/978-3-030-43120-4_26 . ISBN 978-3-030-43119-8. S2CID 201058355 .

[Cormode04-21] كورمود، غراهام (2004). صعوبة لعبة الليمينغ، أو يا إلهي، المزيد من براهين اكتمال NP (PDF) .

[22] الإضاءة مكتملة NP

[Friedman-23] فريدمان، إريك. "ألغاز اللؤلؤ هي NP-كاملة" .

[24] كاي (2000)

[25] آلان سكوت، أولريك ستيج، إيريس فان روي، قد لا تكون لعبة كاسحة الألغام NP-كاملة ولكنها صعبة مع ذلك، The Mathematical Intelligencer 33 :4 (2011)، ص 5-17.

[26] هولزر، ماركوس؛ كلاين، أندرياس؛ كوتريب، مارتن؛ روب، أوليفر (2011). "التعقيد الحسابي لـ NURIKABE". Fundamenta Informaticae . 110 ( 1-4 ): 159-174 . doi : 10.3233/FI-2011-534 .

[27] ناكاي، كينشيرو. تاكيناجا ياسوهيكو (2012). "NP-اكتمال الوباء" . مجلة معالجة المعلومات . 20 (3): 723-726 . دوى : 10.2197/ipsjjip.20.723 . ردمك 1882-6652 .

[28] ديمين، إريك؛ آيزنستات، سارة؛ رودوي، ميخائيل (2018). حل مكعب روبيك الأمثل هو مسألة NP-كاملة . الندوة الخامسة والثلاثون حول الجوانب النظرية لعلوم الحاسوب (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .

[sigal87-29] 1 2 ساتو، تاكايوكي؛ سيتا، تاكاهيرو (1987). تعقيد واكتمال إيجاد حل آخر وتطبيقه على الألغاز (ملف PDF) . الندوة الدولية حول الخوارزميات (SIGAL 1987). مؤرشف من الأصل (ملف PDF) في 3 مارس 2020. تم الاطلاع عليه في 8 أبريل 2017 .

[NU07-30] نوكوي؛ أويجيما (مارس 2007). "اكتمال لغز Slither Link على عدة شبكات باستخدام ASP" . ملاحظات Ipsj Sig . 2007 (23): 129– 136.

[Kölker12c-31] كولكر، جوناس (2012). "متغيرات مختارة من روابط الانزلاق هي مسائل NP-كاملة" . مجلة معالجة المعلومات . 20 (3): 709-712 . doi : 10.2197/ipsjjip.20.709 .

[32] دراسة استقصائية لألغاز NP-الكاملة، القسم 23؛ غراهام كيندال، أندرو باركس، كريستيان سبورر؛ مارس 2008. (icga2008.pdf) مؤرشف في 19 يونيو 2022 في Wayback Machine

[33] ديمين، إريك د.؛ هوهنبرغر، سوزان؛ ليبن-نويل، ديفيد (25-28 يوليو 2003). لعبة تتريس صعبة، حتى التقريب منها (ملف PDF) . وقائع المؤتمر الدولي التاسع للحوسبة والتوافقية (COCOON 2003) . بيغ سكاي، مونتانا.

[34] ليم، أندرو (1998)، "مشكلة تخطيط الرصيف"، رسائل بحوث العمليات ، 22 ( 2-3 ): 105-110 ، doi : 10.1016/S0167-6377(98)00010-8 ، MR 1653377

[35] ج. بونو، "تعدين البيتكوين صعب من نوع NP"

[36] جاليل، تسفي؛ مجدو، نمرود (أكتوبر 1977). "الترتيب الدوري مسألة كاملة من فئة NP" . علوم الحاسوب النظرية . 5 (2): 179-182 . doi : 10.1016/0304-3975(77)90005-6 .

[37] ويتفيلد، جيمس دانيال؛ لوف، بيتر جون؛ أسبورو-جوزيك، آلان (2013). "التعقيد الحسابي في البنية الإلكترونية" . فيزياء كيميائية. كيمياء فيزيائية . 15 (2): 397-411 . arXiv : 1208.3334 . Bibcode : 2013PCCP...15..397W . doi : 10.1039/C2CP42695A . PMID: 23172634. S2CID : 12351374 .

[38] أغول، إيان ؛ هاس، جويل ؛ ثورستون، ويليام (19 مايو 2002). "جنس العقدة ثلاثية الأبعاد هو مسألة NP-كاملة" . وقائع الندوة السنوية الرابعة والثلاثين لجمعية ACM حول نظرية الحوسبة . STOC '02. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 761-766 . arXiv : math/0205057 . doi : 10.1145/509907.510016 . ISBN 978-1-58113-495-7. S2CID 10401375 .

[39] Çivril, Ali; Magdon-Ismail, Malik (2009), “حول اختيار مصفوفة فرعية ذات حجم أقصى من مصفوفة والمشاكل ذات الصلة” (ملف PDF) ، علوم الحاسوب النظرية ، 410 ( 47-49 ): 4801-4811 ، doi : 10.1016/j.tcs.2009.06.018 ، MR 2583677 ، مؤرشف من الأصل (ملف PDF) في 3 فبراير 2015

[40] بيتر داوني، وبنتون ليونغ، ورافي سيثي. "حساب المتتاليات باستخدام سلاسل الجمع" مجلة SIAM للحوسبة، 10(3)، 638-646، 1981

[41] دي جيه بيرنشتاين، "خوارزمية بيبينجر للأس" (مسودة)

[42] هيركنز، سي.؛ إيرسيل، إل. في.؛ كيسبر، ج.؛ كيلك، إس.؛ ستوجي، إل.؛ ترومب، ج. (2007). "انعكاسات البادئات على السلاسل الثنائية والثلاثية". مجلة SIAM للرياضيات المتقطعة . 21 (3): 592-611 . arXiv : math/0602456 . doi : 10.1137/060664252 .

[NP-complete_decision_problems_for_Quadratic_Polynomials-43] 1 2 ماندرز، كينيث؛ أدلمان، ليونارد (1976). "مسائل القرار الكاملة من فئة NP لكثيرات الحدود التربيعية" . وقائع الندوة السنوية الثامنة لجمعية ACM حول نظرية الحوسبة - STOC '76 . الصفحات 23-29 . doi : 10.1145/800113.803627 . ISBN 9781450374149. S2CID 18885088 .

[44] بين، دبليو دبليو؛ لارمور، إل إل؛ لطيفي، إس؛ سودبورو، آي إتش (1 يناير 2002). "فرز الكتل صعب". وقائع الندوة الدولية حول البنى المتوازية والخوارزميات والشبكات. I-SPAN'02 . الصفحات 307-312 . doi : 10.1109/ISPAN.2002.1004305 . ISBN 978-0-7695-1579-3. S2CID 32222403 .

[45] باري آرثر سيبرا ، "نموذج إيزينغ كامل من النوع NP"، أخبار SIAM، المجلد 33، العدد 6.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[

[

[ 29 ]

[ 30 ]

[ 31 ]

[

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[ 45 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗