۲۱ مسئله انپی-کامل کارپ
۲۱ مسئله انپی-کامل کارپ دربردارندۀ ۲۱ مسئلهای است که ریچارد کارپ در مقالهاش «کاهشپذیری میان مسئلههای ترکیبی» نشان داد که ان پی کاملاند. پیش از این، استیون کوک نشان داده بود که صدقپذیری دودویی انپی کامل است. کارپ توانست صدقپذیری دودویی را به ۲۱ مسئلۀ دیگر بکاهد و پیچیدگیشان را نشان دهد. مقالۀ کارپ در سال ۱۹۷۲ چاپ شد و پژوهشهای گستردهای را در زمینههای انپی-کامل و برابری پی و انپی در پی داشت. از همین روی، کارپ جایزه تورینگ را در سال ۱۹۸۵ دریافت کرد.
مسئلهها
کارپ ۲۱ مورد زیر را که بررسی کرد:
- صدقپذیری دودویی: ارزشدهی به متغیرهای گزارهای دودویی به گونهای که گزاره ارزش درست بگیرد.
- کاهش از: -
- درونداد (ورودی): گزارۀ هنجار (نرمال)
- برونداد (خروجی): ارزش درست یا نادرست برای هر یک از درایههای به گونهای که ارزشنیز درست باشد.
- برنامهنویسی درست دودویی:
- کاهش از: صدقپذیری دودویی
- درونداد: ماتریس درست و بردار درست
- برونداد: بردار دودویی هست که
- گروهک (مجموعه ناوابسته را هم ببینید)
- کاهش از: صدقپذیری دودویی
- درونداد: گراف و عدد درست
- برونداد: گروهکی با گره
- بستهبندی مجموعه
- کاهش از: گروهک
- درونداد: مجموعۀ و برخی از زیرمجموعههایشو عدد درست()
- برونداد: زیرمجموعۀکه از هم سوایند (هیچ هموند یکسانی ندارند)
- پوشش گرهای: در گراف، زیرمجموعهای از گرهها که دستکم یکی از گرههای دو سر هر یال در این زیرمجموعه باشد.
- پوشش مجموعه
- کاهش از: پوشش گرهای
- درونداد: خانوادهای محدود از مجموعههای محدود ، عدد درست مثبت k
- برونداد: یک زیرخانواده وجود دارد که زیرمجموعهاست و شامل کمتر یا برابر بامجموعه است به طوری که
- مجموعه گرههای بازخورد: یافتن گرههایی از گراف که اگر این گرهها از گراف برداشته شوند، گراف دیگر هیچ دوری نخواهد داشت.
- کاهش از: پوشش گرهای
- درونداد: گراف و عدد درست
- برونداد: گرۀ بازخورد
- FEEDBACK ARC SET(مسئله مجموعه یالهای پسخورد)
- DIRECTED HAMILTONIAN CIRCUIT(مسئله دور مستقیم همیلتونی)
- UNDIRECTED HAMILTONIAN CIRCUIT(مسئله دور غیرمستقیم همیلتونی)
- ۳SAT(مسئله ۳SAT)
- رنگآمیزی گراف
- پوشش گروهک
- EXACT COVER(پوشش دقیق)
- HITTING SET(مجموعه ضربهزننده)
- درخت اشتاینر
- تطابق سهبعدی
- کولهپشتی
- زمانبندی کارها
- مسئله تقسیمبندی
- برش بیشینه
پانویس
- ↑ Karp, Richard (1972). Reducibility among combinatorial problems.
منبعها
- 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
بیشتر بخوانید
- 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». بایگانیشده از اصلی در ۲۷ ژوئیه ۲۰۱۰. دریافتشده در ۱۰ ژوئیه ۲۰۰۸.
- «فهرستی از نوشتههای ریچارد کارپ». بایگانیشده از اصلی در ۱۴ مه ۲۰۰۸. دریافتشده در ۱۰ ژوئیه ۲۰۰۸.