۲۱ مسئله ان‌پی-کامل کارپ

۲۱ مسئله ان‌پی-کامل کارپ شامل ۲۱ مسئله‌ای است که ریچارد کارپ در مقاله برجسته خود با عنوان «ساده‌سازی در مسائل ترکیبی» ثابت کرد که ان‌پی-کامل هستند. این مقاله تأثیرگرفته از نتایج بسیار مهم استفان کوک در نظریه پیچیدگی محاسباتی است که اثبات اولین مسئله ان‌پی-کامل یعنی مسئله رضایت بولی بود. مقاله کارپ که در سال ۱۹۷۲ منتشر شد، باعث شد تا تحقیقات گسترده‌ای در زمینه‌های ان‌پی، ان‌پی-کامل و سؤال مشهور مسئله برابری پی و ان‌پی شکل بگیرد و همچنین یکی از مهم‌ترین دلایلی بود که جایزه تورینگ در سال ۱۹۸۵ به او تعلق گرفت.

مسائل

1. SAT(مسئله رضایت بولی): مسئله تعیین درستی متغیرهای یک عبارت بولی به طوری که کل عبارت درست باشد.
2. ۰-۱ INTEGER PROGRAMMING(برنامه‌نویسی خطی اعداد صحیح )
   • ورودی: ماتریس صحیح C و بردار صحیح d
   • ویژگی: بردار دودویی x وجود دارد که Cx=d.
3. CLIQUE یا independent set problem(مسئله گروهک یا مسئله مجموعه مستقل)
   • ورودی: گراف G، عدد صحیح مثبت k
   • ویژگی: G دارای زیرگراف کامل با k رأس است.
4. SET PACKING(مسئله بسته‌بندی مجموعه)
   • ورودی: خانواده‌ای از مجموعه‌های $\{S_j\}$، عدد صحیح مثبت k
   • ویژگی: $\{S_j\}$ شامل k مجموعه جدا از هم است.
5. VERTEX COVER(مسئله پوشش رأس)
   • ورودی: گراف G، عدد صحیح مثبت k
   • ویژگی: زیرمجموعه‌ای r عضوی از رئوس گراف وجود دارد که $r \le k$ و حداقل یک طرف هر یال به عضوی از این زیرمجموعه می‌رسد.
6. SET COVERING(مسئله پوشش مجموعه)
   • ورودی: خانواده‌ای محدود از مجموعه‌های محدود $\{S_j\}$، عدد صحیح مثبت k
   • ویژگی: یک زیرخانواده $\{T_h\}$ وجود دارد که زیرمجموعه $\{S_j\}$ است و شامل کمتر یا مساوی k مجموعه است به طوری که $\bigcup \{S_j\}=\bigcup \{T_h\}$
7. FEEDBACK NODE SET(مسئله مجموعه رئوس پس‌خورد)
8. FEEDBACK ARC SET(مسئله مجموعه یال‌های پس‌خورد)
9. DIRECTED HAMILTONIAN CIRCUIT(مسئله دور مستقیم همیلتونی)
10. UNDIRECTED HAMILTONIAN CIRCUIT(مسئله دور غیرمستقیم همیلتونی)
11. ۳SAT(مسئله ۳SAT)
12. CHROMATIC NUMBER یا Graph Coloring Problem(مسئله عدد رنگی گراف یا مسئله رنگ‌آمیزی گراف)
13. CLIQUE COVER(مسئله پوشش گروهک)
14. EXACT COVER(مسئله پوشش دقیق)
15. HITTING SET(مسئله مجموعه ضربه‌زننده)
16. STEINER TREE(مسئله درخت اشتاینر)
17. ۳D MATCHING(مسئله تطابق سه‌بعدی)
18. KNAPSACK یا Subset sum(مسئله کوله‌پشتی یا صورت کلی‌تر آن مسئله حاصل‌جمع زیرمجموعه)
19. JOB SEQUENCING(مسئله ترتیب‌دهی شغل)
20. PARTITION(مسئله تفکیک)
21. MAX-CUT(مسئله بیشترین برش)

منابع

• Richard M. Karp. “Reducibility Among Combinatorial Problems”. In Complexity of Computer Computations. R. E. Miller and J. W. Thatcher (editors). New York: Plenum, 1972. 85–103. 

• مشارکت‌کنندگان ویکی‌پدیا، «Karp's 21 NP-complete problems»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲ ژوئیه ۲۰۰۸).

مطالعه بیشتر

• Stephen Cook. “The Complexity of Theorem Proving Procedures”. In Proceedings of the third annual ACM symposium on Theory of computing. 1971. 151–158. 
• David Zuckerman. On Unapproximable Versions of NP-Complete Problems. . SIAM Journal on Computing 25, no. 6 (1996): 1293–1304. 

پیوند به بیرون

• «NP-Complete در سایت Complexity Zoo». 

• «لیستی از انتشارات ریچارد کارپ».