ⓘ ان‌پی کامل. در نظریه پیچیدگی محاسباتی NPیکی از بنیادی‌ترین کلاس‌ها است. NP مخفف عبارت Non-Deterministic Polynomial است که به زمان اجرای آن اشاره دارد. NP مجموعه ..

                                     

ⓘ ان‌پی کامل

در نظریه پیچیدگی محاسباتی NPیکی از بنیادی‌ترین کلاس‌ها است. NP مخفف عبارت "Non-Deterministic Polynomial" است که به زمان اجرای آن اشاره دارد. NP مجموعهٔ کلیه مسائل تصمیم‌گیری است که پیدا کردن جواب بله برای آن‌ها شامل اثبات ساده‌ای است که جواب حقیقتاً باید بله باشد. به‌طور دقیق تر این اثبات‌های ساده باید قابل بررسی در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ قطعی باشد. در مقابل این تعریف NP مجموعه مسائل تصمیم‌گیری نامیده می‌شود که در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ غیرقطعی قابل بررسی باشند. کلاس پیچیدگی P یکی از اعضای NP است اما NP شامل کلاس‌های مهم دیگری نیز هست؛ که پیچیده‌ترین آن‌ها NP-Complete است به‌طوری‌که برای آن‌ها هیچ الگوریتم شناخته شده قابل اجرا در زمان چندجمله‌ای وجود ندارد. مهمترین سؤالی که اکنون برای این کلاس‌ها در این نظریه وجود دارد این است که آیا P=NP؟ این سؤال می‌پرسد که آیا چنین الگوریتمی واقعاً برای مسائل NP-Complete و در کل NP وجود دارد یا خیر. این باور گسترده وجود دارد که این تساوی نمی‌تواند درست باشد.

                                     

1. مقدمه

بسیاری از مسئله‌های معمول علوم کامپیوتر در حوزهٔ مسائل NP قرار دارند. مخصوصاً مدل تصمیم‌گیری بسیاری از مسائل جستجو و بهینه‌سازی در حوزهٔ NP قرار دارد. نمونه‌هایی از زمینه‌هایی که شامل مسائل NP می‌شوند عبارتند از: مانند جبر بولی، گراف، طراحی شبکه، زیست‌شناسی، فیزیک جدید، نظریه اعداد، نظریه بازی‌ها و پازل‌ها، نظریه زبان‌ها و ماشین‌ها و.

                                     

1.1. مقدمه تعریف بر پایهٔ بررسی‌کننده

به منظور تعریف این چنین NP بیایید مسئلهٔ مجموع زیر مجموعه‌ها را در نظر بگیرید. فرض کنید به ما تعدادی عدد صحیح داده شده‌است مثلاً {-۷و-۳و-۲ ۵و ۸و} و ما می‌خواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه‌های آن صفر می‌شود یا نه؟ در این مثال جواب بله است زیرا اعداد −۳، ۵ و −۲ می‌توانند این شرط را بررسی کنند.

هنگامیکه مقدار اعداد صحیح ورودی زیاد شود تعداد زیر مجموعه‌ها به صورت توانی افزایش می‌یابد و در حقیقت مسئله فوق یک مسئله NP-Complete است.

در هر حال توجه شود که اگر به ما یک زیر مجموعه مشخص بدهند بعضی اوقات گواه نامیده می‌شود ما به راحتی می‌توانیم بررسی کنیم که آیا مجموع آن صفر است یا خیر. تنها با جمع کردن اعضای آن زیر مجموعه و اگر مجموع صفر باشد آن زیر مجموعه یک شاهد برای این است که جواب بله است. الگوریتمی که بررسی می‌کند آیادرزیر مجموعه داده شده مجموع اعضا صفر است بررسی‌کننده نامیده می‌شود.

یک مسئله را عضو NP می‌نامند اگر و فقط اگر یک بررسی‌کننده برای آن وجود داشته باشد که در زمان اجرای چندجمله‌ای اجرا شود.

در مورد مسئله مجموع زیر مجموعه‌ها نیز بررسی‌کننده تنها نیازمند زمان اجرای خطی است که این دلیلی است برای اینکه این مسئله NP است.

توجه شود که در تعریف بر پایهٔ بررسی‌کننده NP نیازمند یک بررسی‌کننده به عنوان گواه برای جواب نه نیست. آن کلاس مسائلی که شامل یک شاهد این چنینی هستند CO-NP نامیده می‌شود. در حقیقت یک سؤال بدون جواب دیگری در اینجا وجود دارد که آیا تمام مسائل NP دارای یک گواه برای جواب نه هستند و در نتیجه CO-NP می‌شوند.

                                     

1.2. مقدمه تعریف ماشینی

معادل تعاریف قبلی این تعریف نیز وجود دارد که می‌گوید: NP مجموعه مسائل تصمیم‌گیری است که قابل حل شدن در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ غیرقطعی می‌باشد.

مثال در اینجا یک فهرست نا کامل از مسائل NP را بیان می‌کنیم: تمام مسائل P (برای یک گواه مسئله P ما می‌توانیم کلاً گواه را نادیده بگیریم و مسئله را در زمان اجرای چندجمله‌ای حل کرد. همچنین توجه شود که یک ماشین تورینگ قطعی یک ماشین تورینگ غیر قطعی است که از هیچ‌کدام از توانایی‌های غیرقطعی اش استفاده نمی‌کند. مسئله پیدا کردن مقسوم علیه‌های یک عدد صحیح: دو عدد صحیح N و K داده شده‌اند. می‌خواهیم بدانیم آیا عدد صحیحی مثل F وجود دارد که ۱

                                     
  • مسئله ان پی - کامل کارپ دربردارندۀ مسئله ای است که ریچارد کارپ در مقاله اش کاهش پذیری میان مسئله های ترکیبی نشان داد که ان پی کاملاند. پیش از این
  • مجموعه ان پی - سخت شامل چندهزار مسئله مختلف با کاربردهای فراوان است که تاکنون برای آن ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال
  • ان - پی کامل قوی در نظریه ی پیچیدگی محاسباتی ان - پی کامل قوی بودن یک ویژگی مسایل محاسباتی است که حالت خاصی از ان - پی کامل بودن است. یک مسئله محاسباتی در
  • باشند فرمول همواره درست است. پرسمان صدق پذیری نخستین پرسمانی است که ان پی کامل بودنش نشان داده شده است. کوک و لوین نشان دادند الگوریتمی شناخته شده ای
  • بسته بندی مجموعه یک مسئله ان پی کامل کلاسیک در نظریه پیچیدگی محاسباتی و ترکیب شناسیست و یکی از مسئله ان پی - کامل کارپ می باشد. فرض کنید ما یک مجموعه
  • دودویی مسئله ای ان پی کامل است: الگوریتم نمی شناسیم که در زمانی کوتاه مسئله صدق پذیری را حل کند. این مسئله نخستین مسئله ای است که ان پی کامل بودنش نشان داده
  • برابری پی و ان پی را مطرح کرد. او این مسئله را در نامه ای به جان فون نویمان مطرح کرده بود و از او پرسیده بود ایا مشکلات و مسائل مشخص ان پی کامل با زمان
  • گره ای می پردازد که کم ترین شمار گره ها را دربرداشته باشد. این پرسمان ان پی کامل است از این روی رایانش چنین زیرمجموعه ای دشوار است. برای گرافی بی سو مانند
  • محاسباتی این یک مسآله ترکیبیات ان پی سخت است. مسئله تصمیم تصمیم اینکه تعداد مشخص از جعبه بهینه است این مشکل یک ان پی کامل است. مسئله تقسیم بندی مسئله جمع
  • مقدار ورودی اجرا می شوند. واژه NP کامل بدین معنی است که یک مسئله ارزش این را ندارد که سعی شود به صورت بهینه کامل حل شود. توماس اچ کورمن Charles E.