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

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

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

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

کارپ ۲۱ مورد زیر را که بررسی کرد:

  1. صدق‌پذیری دودویی: ارزش‌دهی به متغیرهای گزاره‌ای دودویی به گونه‌ای که گزاره ارزش درست بگیرد.
    • کاهش از: -
    • درون‌داد (ورودی): گزارۀ هنجار (نرمال)
    • برون‌داد (خروجی): ارزش درست یا نادرست برای هر یک از درایه‌های به گونه‌ای که ارزش نیز درست باشد.
  2. برنامه‌نویسی درست دودویی:
  3. گروهک (مجموعه ناوابسته را هم ببینید)
    • کاهش از: صدق‌پذیری دودویی
    • درون‌داد: گراف و عدد درست
    • برون‌داد: گروهکی با گره
  4. بسته‌بندی مجموعه
    • کاهش از: گروهک
    • درون‌داد: مجموعۀ و برخی از زیرمجموعه‌هایش و عدد درست ()
    • برون‌داد: زیرمجموعۀ که از هم سوایند (هیچ هموند یکسانی ندارند)
  5. پوشش گره‌ای: در گراف، زیرمجموعه‌ای از گره‌ها که دست‌کم یکی از گره‌های دو سر هر یال در این زیرمجموعه باشد.
    • کاهش از: گروهک
    • درون‌داد: گراف و عدد درست
    • برون‌داد: پوشش گره‌ای به اندازۀ
  6. پوشش مجموعه
    • کاهش از: پوشش گره‌ای
    • درون‌داد: خانواده‌ای محدود از مجموعه‌های محدود ، عدد درست مثبت k
    • برون‌داد: یک زیرخانواده وجود دارد که زیرمجموعه است و شامل کمتر یا برابر با مجموعه است به طوری که
  7. مجموعه گره‌های بازخورد: یافتن گره‌هایی از گراف که اگر این گره‌ها از گراف برداشته شوند، گراف دیگر هیچ دوری نخواهد داشت.
  8. FEEDBACK ARC SET(مسئله مجموعه یال‌های پس‌خورد)
  9. DIRECTED HAMILTONIAN CIRCUIT(مسئله دور مستقیم همیلتونی)
  10. UNDIRECTED HAMILTONIAN CIRCUIT(مسئله دور غیرمستقیم همیلتونی)
  11. ۳SAT(مسئله ۳SAT)
  12. رنگ‌آمیزی گراف
  13. پوشش گروهک
  14. EXACT COVER(پوشش دقیق)
  15. HITTING SET(مجموعه ضربه‌زننده)
  16. درخت اشتاینر
  17. تطابق سه‌بعدی
  18. کوله‌پشتی
  19. زمان‌بندی کارها
  20. نخشدی
  21. برش بیشینه

پانویس[ویرایش]

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

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

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

بیش‌تر بخوانید[ویرایش]

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