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

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

1. صدق‌پذیری دودویی: ارزش‌دهی به متغیرهای گزاره‌ای دودویی به گونه‌ای که گزاره ارزش درست بگیرد.
   • کاهش از: -
   • درون‌داد (ورودی): گزارۀ هنجار (نرمال) ${\displaystyle X=(x_{1}\land x_{2}\land \dots \land x_{m})\lor (y_{1}\land y_{2}\land \dots \land y_{n})\lor \dots }$
   • برون‌داد (خروجی): ارزش درست یا نادرست برای هر یک از درایه‌های ${\displaystyle X}$
     به گونه‌ای که ارزش ${\displaystyle X}$
     نیز درست باشد.
2. برنامه‌نویسی درست دودویی:
   • کاهش از: صدق‌پذیری دودویی
   • درون‌داد: ماتریس درست ${\displaystyle C}$
     و بردار درست ${\displaystyle d}$
   • برون‌داد: بردار دودویی ${\displaystyle x}$
     هست که ${\displaystyle Cx=d}$
3. گروهک (مجموعه ناوابسته را هم ببینید)
   • کاهش از: صدق‌پذیری دودویی
   • درون‌داد: گراف ${\displaystyle G}$
     و عدد درست ${\displaystyle k>0}$
   • برون‌داد: گروهکی با ${\displaystyle k}$
     گره
4. بسته‌بندی مجموعه
   • کاهش از: گروهک
   • درون‌داد: مجموعۀ ${\displaystyle S}$
     و برخی از زیرمجموعه‌هایش ${\displaystyle \{S_{1},S_{2},\dots ,S_{n}\}}$
     و عدد درست ${\displaystyle k>0}$
     (${\displaystyle k\leq n}$
     )
   • برون‌داد: ${\displaystyle k}$
     زیرمجموعۀ ${\displaystyle S_{j}}$
     که از هم سوایند (هیچ هموند یکسانی ندارند)
5. پوشش گره‌ای: در گراف، زیرمجموعه‌ای از گره‌ها که دست‌کم یکی از گره‌های دو سر هر یال در این زیرمجموعه باشد.
   • کاهش از: گروهک
   • درون‌داد: گراف ${\displaystyle G}$
     و عدد درست ${\displaystyle k>0}$
   • برون‌داد: پوشش گره‌ای به اندازۀ ${\displaystyle k}$
6. پوشش مجموعه
   • کاهش از: پوشش گره‌ای
   • درون‌داد: خانواده‌ای محدود از مجموعه‌های محدود ${\displaystyle \{S_{j}\}}$
     ، عدد درست مثبت k
   • برون‌داد: یک زیرخانواده ${\displaystyle \{T_{h}\}}$
     وجود دارد که زیرمجموعه ${\displaystyle \{S_{j}\}}$
     است و شامل کمتر یا برابر با ${\displaystyle k}$
     مجموعه است به طوری که ${\displaystyle \bigcup \{S_{j}\}=\bigcup \{T_{h}\}}$
7. مجموعه گره‌های بازخورد: یافتن گره‌هایی از گراف که اگر این گره‌ها از گراف برداشته شوند، گراف دیگر هیچ دوری نخواهد داشت.
   • کاهش از: پوشش گره‌ای
   • درون‌داد: گراف ${\displaystyle G}$
     و عدد درست ${\displaystyle k>0}$
   • برون‌داد: ${\displaystyle k}$
     گرۀ بازخورد
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. برش بیشینه

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

• «NP-Complete در سایت Complexity Zoo». بایگانی‌شده از اصلی در ۲۷ ژوئیه ۲۰۱۰. دریافت‌شده در ۱۰ ژوئیه ۲۰۰۸.

• «فهرستی از نوشته‌های ریچارد کارپ». بایگانی‌شده از اصلی در ۱۴ مه ۲۰۰۸. دریافت‌شده در ۱۰ ژوئیه ۲۰۰۸.