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

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

مسئله‌ها

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

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

منبع‌ها

• Richard M. Karp (1972), "Reducibility Among Combinatorial Problems", Complexity of Computer Computations (PDF) (به انگلیسی), به کوشش R. E. Miller and J. W. Thatcher (editors)., New York: Plenum, p. 85–103, archived from the original (PDF) on 29 June 2011, retrieved 2 July 2008

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

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

• Stephen Cook (1971), "The Complexity of Theorem Proving Procedures", Proceedings of the third annual ACM symposium on Theory of computing (به انگلیسی), p. 151–158
• David Zuckerman (1996), "On Unapproximable Versions of NP-Complete Problems", SIAM Journal on Computing (به انگلیسی), vol. 25, p. 1293–1304, doi:10.1137/S0097539794266407

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

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

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