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

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

مسئله‌ها 
کارپ ۲۱ مورد زیر را که بررسی کرد:
 صدق‌پذیری دودویی: ارزش‌دهی به متغیرهای گزاره‌ای دودویی به گونه‌ای که گزاره ارزش درست بگیرد.
 کاهش از: -
 درون‌داد (ورودی): گزارۀ هنجار (نرمال) 
 برون‌داد (خروجی): ارزش درست یا نادرست برای هر یک از درایه‌های  به گونه‌ای که ارزش   نیز درست باشد.
 برنامه‌نویسی درست دودویی:
 کاهش از: صدق‌پذیری دودویی
 درون‌داد: ماتریس درست  و بردار درست 
 برون‌داد: بردار دودویی  هست که 
 گروهک (مجموعه ناوابسته را هم ببینید)
 کاهش از: صدق‌پذیری دودویی
 درون‌داد: گراف  و عدد درست 
 برون‌داد: گروهکی با  گره
 بسته‌بندی مجموعه
 کاهش از: گروهک
 درون‌داد: مجموعۀ  و برخی از زیرمجموعه‌هایش  و عدد درست  ()
 برون‌داد:  زیرمجموعۀ  که از هم سوایند (هیچ هموند یکسانی ندارند)
 پوشش گره‌ای: در گراف، زیرمجموعه‌ای از گره‌ها که دست‌کم یکی از گره‌های دو سر هر یال در این زیرمجموعه باشد.
 کاهش از: گروهک
 درون‌داد: گراف  و عدد درست 
 برون‌داد: پوشش گره‌ای به اندازۀ 
 پوشش مجموعه
 کاهش از: پوشش گره‌ای
 درون‌داد: خانواده‌ای محدود از مجموعه‌های محدود ، عدد درست مثبت k
 برون‌داد: یک زیرخانواده  وجود دارد که زیرمجموعه  است و شامل کمتر یا برابر با  مجموعه است به طوری که 
 مجموعه گره‌های بازخورد: یافتن گره‌هایی از گراف که اگر این گره‌ها از گراف برداشته شوند، گراف دیگر هیچ دوری نخواهد داشت. 
 کاهش از: پوشش گره‌ای
 درون‌داد: گراف  و عدد درست 
 برون‌داد:  گرۀ بازخورد
 FEEDBACK ARC SET(مسئله مجموعه یال‌های پس‌خورد)
 DIRECTED HAMILTONIAN CIRCUIT(مسئله دور مستقیم همیلتونی)
 UNDIRECTED HAMILTONIAN CIRCUIT(مسئله دور غیرمستقیم همیلتونی)
 ۳SAT(مسئله ۳SAT)
 رنگ‌آمیزی گراف
 پوشش گروهک
 EXACT COVER(پوشش دقیق)
 HITTING SET(مجموعه ضربه‌زننده)
 درخت اشتاینر
 تطابق سه‌بعدی
 کوله‌پشتی
 زمان‌بندی کارها
 مسئله تقسیم‌بندی
 برش بیشینه

پانویس

منبع‌ها

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

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

 

پیچیدگی محاسباتی
فهرست‌های ریاضی
مسئله‌های ان‌پی کامل