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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

مسائل[ویرایش]

  1. SAT(مسئله رضایت بولی): مسئله تعیین درستی متغیرهای یک عبارت بولی به طوری که کل عبارت درست باشد.
  2. ۰-۱ INTEGER PROGRAMMING(برنامه‌نویسی خطی اعداد صحیح )
    • ورودی: ماتریس صحیح C و بردار صحیح d
    • ویژگی: بردار دودویی x وجود دارد که Cx=d.
  3. CLIQUE یا independent set problem(مسئله گروهک یا مسئله مجموعه مستقل)
  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(مسئله بیشترین برش)

منابع[ویرایش]

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

مطالعه بیشتر[ویرایش]

پیوند به بیرون[ویرایش]