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

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

۲۱ مسئله ان‌پی-کامل کارپ دربردارنده‌ی ۲۱ مسئله ای است که ریچارد کارپ در مقاله‌‌اش «کاهش‌پذیری میان مسئله های ترکیبی» [۱] نشان داد که ان پی کامل هستند. پیش از این مقاله، استیون کوک نشان داده بود که مسئله صدق‌پذیری دودویی ان‌‌پی کامل است. کارپ با این کاهش دادن مسئله به ۲۱ مسئله یاد شده ان‌پی کامل بودن این مسئله ها را نشان داد. مقاله‌ی کارپ در سال ۱۹۷۲ چاپ شد و پژوهش‌های گسترده‌ای را در زمینه‌های ان‌پی-کامل و مسئله برابری پی و ان‌پی در پی داشت. از همین روی بود که کارپ جایزه تورینگ را در سال ۱۹۸۵ دریافت کرد.

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

  1. مسئله صدق‌پذیری دودویی: مسئله ارزش‌دهی به متغیرهای عبارتی دودویی به گونه‌ای که عبارت ارزش درست بگیرد.
    • درون‌داد (ورودی): عبارت هنجار (نرمال)
    • برون‌داد (خروجی): ارزش درست یا نادرست برای هر یک از درایه‌های به گونه‌ای که ارزش نیز درست باشد.
  1. برنامه‌نویسی درست دودویی
    • درون‌داد: ماتریس درست و بردار درست
    • برون‌داد: بردار دودویی هست که
  2. مسئله گروهک (مسئله مجموعه ناوابسته را هم ببینید)
    • درون‌داد: گراف و عدد درست مثبت
    • برون‌داد: گروهکی با گره
  3. بسته‌بندی مجموعه
    • درون‌داد: مجموعه‌ی و برخی از زیرمجموعه‌هایش و عدد درست مثبت ()
    • برون‌داد: زیرمجموعه‌ی که از هم سوایند (هیچ هموند یکسانی ندارند)
  4. مسئله پوشش گره‌ای: در گراف، زیرمجموعه‌ای از گره‌ها که دست‌کم یکی از گره‌های دو سر هر یال در این زیرمجموعه باشد.
    • درون‌داد: گراف و عدد درست مثبت
    • برون‌داد: پوشش گره‌ای به اندازه‌ی
  5. مسئله پوشش مجموعه
    • درون‌داد: خانواده‌ای محدود از مجموعه‌های محدود ، عدد صحیح مثبت k
    • ویژگی: یک زیرخانواده وجود دارد که زیرمجموعه است و شامل کمتر یا مساوی k مجموعه است به طوری که
  6. FEEDBACK NODE SET(مسئله مجموعه رئوس پس‌خورد)
  7. FEEDBACK ARC SET(مسئله مجموعه یال‌های پس‌خورد)
  8. DIRECTED HAMILTONIAN CIRCUIT(مسئله دور مستقیم همیلتونی)
  9. UNDIRECTED HAMILTONIAN CIRCUIT(مسئله دور غیرمستقیم همیلتونی)
  10. ۳SAT(مسئله ۳SAT)
  11. CHROMATIC NUMBER یا Graph Coloring Problem(مسئله عدد رنگی گراف یا مسئله رنگ‌آمیزی گراف)
  12. CLIQUE COVER(مسئله پوشش گروهک)
  13. EXACT COVER(مسئله پوشش دقیق)
  14. HITTING SET(مسئله مجموعه ضربه‌زننده)
  15. STEINER TREE(مسئله درخت اشتاینر)
  16. ۳D MATCHING(مسئله تطابق سه‌بعدی)
  17. KNAPSACK یا Subset sum(مسئله کوله‌پشتی یا نسخه ی تصمیمی آن مسئله حاصل‌جمع زیرمجموعه)
  18. JOB SEQUENCING(مسئله ترتیب‌دهی شغل)
  19. PARTITION(مسئله تفکیک)
  20. MAX-CUT(مسئله بیشترین برش)

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

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

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

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

  • Karp, Richard (1972). Reducibility among combinatorial problems.