موضوع مقاله: NP (پیچیدگی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # NP (پیچیدگی) | مقدمه: NP مجموعهٔ کلیه مسائل تصمیم‌گیری است که پیدا کردن جواب بله برای آن‌ها شامل اثبات ساده‌ای است که جواب حقیقتاً باید بله باشد. | ## بخش 1: NP (پیچیدگی) | به‌طور دقیق تر این اثبات‌های ساده باید قابل بررسی در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ جبری باشد. در مقابل این تعریف NP مجموعه مسائل تصمیم‌گیری نامیده می‌شود که در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ غیر جبری قابل بررسی باشند. کلاس پیچیدگی P یکی از اعضای NP است اما NP شامل کلاس‌های مهم دیگری نیز هست؛ که پیچیده‌ترین آن‌ها NP-Complete است بطوریکه برای آن‌ها هیچ الگوریتم شناخته شده قابل اجرا در زمان چندجمله‌ای وجود ندارد. مهمترین سؤالی که اکنون برای این کلاس‌ها در این نظریه وجود دارد این است که آیا P=NP؟ مخصوصاً مدل تصمیم‌گیری بسیاری از مسائل جستجو و بهینه‌سازی در حوزهٔ NP قرار دارد. نمونه‌هایی از زمینه‌هایی که شامل مسائل NP می‌شوند عبارتند از: مانند جبر بولی، گراف، طراحی شبکه، زیست‌شناسی، فیزیک جدید، نظریه اعداد، نظریه بازی‌ها و پازل‌ها، نظریه زبان‌ها و ماشین‌ها و… تعریف بر پایهٔ بررسی کننده به منظور تعریف این چنین NP بیایید مسئلهٔ مجموع زیر مجموعه‌ها را در نظر بگیرید. فرض کنید به ما تعدادی عدد صحیح داده شده‌است مثلاً {-۷و-۳و-۲ ۵و ۸و} و ما می‌خواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه‌های آن صفر می‌شود یا نه؟ هنگامیکه مقدار اعداد صحیح ورودی زیاد شود تعداد زیر مجموعه‌ها به صورت توانی افزایش می‌یابد و در حقیقت مسئله فوق یک مسئله NP-Complete است. در هر حال توجه شود که اگر به ما یک زیر مجموعه مشخص بدهند (بعضی اوقات گواه نامیده می‌شود) ما به راحتی می‌توانیم بررسی کنیم که آیا مجموع آن صفر است یا خیر. (تنها با جمع کردن اعضای آن زیر مجموعه) و اگر مجموع صفر باشد آن زیر مجموعه یک شاهد برای این است که جواب بله‌است. الگوریتمی که بررسی می‌کند آیادرزیر مجموعه داده شده مجموع اعضا صفر است بررسی‌کننده نامیده می‌شود. یک مسئله را عضو NP می‌نامند اگر و فقط اگر یک بررسی‌کننده برای آن وجود داشته باشد که در زمان اجرای چندجمله‌ای اجرا شود. در مورد مسئله مجموع زیر مجموعه‌ها نیز بررسی‌کننده تنها نیازمند زمان اجرای خطی است که این دلیلی است برای اینکه این مسئله NP است. توجه شود که در تعریف بر پایهٔ بررسی‌کننده NP نیازمند یک بررسی‌کننده به عنوان گواه برای جواب نه نیست. در حقیقت یک سؤال بدون جواب دیگری در اینجا وجود دارد که آیا تمام مسائل NP دارای یک گواه برای جواب نه هستند و در نتیجه CO-NP می‌شوند. تعریف ماشینی معادل تعاریف قبلی این تعریف نیز وجود دارد که می‌گوید: NP مجموعه مسائل تصمیم‌گیری است که قابل حل شدن در یک زمان اجرای چندجمله‌ای در یک ماشین تورینگ غیر جبری می‌باشد. مثال در اینجا یک لیست نا کامل از مسائل NP را بیان می‌کنیم: تمام مسائل P (برای یک گواه مسئله P ما می‌توانیم کلاً گواه را نادیده بگیریم و مسئله را در زمان اجرای چندجمله‌ای حل کرد. | ## بخش 2: NP (پیچیدگی) | همچنین توجه شود که یک ماشین تورینگ جبری یک ماشین تورینگ غیر جبری است که از هیچ‌کدام از توانایی‌های غیر جبری اش استفاده نمی‌کند. حالت‌های متفاوت مسئله دست فروش دوره گرد که در آن می‌خواهیم بدانیم آیا مسیری هست که از تمام گره‌ها در یک شبکه عبور کند. مسئله درستی منطقی که در آن می‌خواهیم بدانیم آیا یک فرمول منطقی در زبان منطق می‌تواند به ازای مقادیری از متغیرها راست باشد یا خیر. برابری تعاریف دو تعریف برای NP یکی به عنوان مجموعه مسائلی که قابل حل با ماشین تورینگ غیر جبری در زمان اجرای چندجمله‌ای هستند و دیگری مجموعه مسائلی که دارای یک بررسی‌کننده با زمان اجرای چندجمله‌ای در یک ماشین تورینگ جبری هستند با هم معادلند. (این کار تنها نیازمند مراحل چند جمله گونه‌است زیرا این ماشین می‌تواند با حرکات غیر جبری کاراکتر بعدی را در رشتهٔ مورد نظر را در هر مرحله پیدا کند و طول رشتهٔ داده شده نیز باید محدود به چندجمله‌ای باشد) اگر یکی از این رشته‌های بررسی‌کننده معتبر باشد بعضی از مسیرها مورد قبول واقع می‌شوند و اگر هیچ رشته‌ای معتبر نباشد رشته یک زبان به حساب نمی‌آید و پس داده می‌شود. از طرف دیگر فرض کنیم ما یک ماشین تورینگ غیر جبری به نام A داشته باشیم و یک زبان L به آن ارائه کنیم. در هر کدام از مراحل با شمار چندجمله‌ای این ماشین، شاخه‌های درخت محاسبه با یک عدد صحیح ثابت مشخص می‌شوند که نشان دهندهٔ جهت هاست. وجود حداقل یک راه درست الزامی است و رشته‌ای که این مسیر را مشخص می‌کند گواهی برای بررسی کننده‌است. پس از آن اثبات‌کننده می‌تواند به صورت جبری A را به صورت عبور از مسیر پذیرفته شده و بررسی اینکه ار آخر نیز پذیرفته می‌شود پیاده‌سازی کند. اگر A داده را قبول نکند هیچ راه پذیرفته شده‌ای وجود ندارد و بررسی‌کننده هیچ‌گاه به جواب بله نمی‌رسد. به این علت که بسیاری مسئلهٔ مهم در این کلاس وجود دارد تلاش‌های فراوانی برای پیدا کردن الگوریتم‌هایی با زمان اجرای چندجمله‌ای برای مسائل NP صورت گرفته‌است. با این وجود باز هم مسائلی از NP باقی می‌مانند که در برابر این تلاش‌ها مقاومت می‌کنند و به نظر می‌رسد که نیازمند زمان اجرای فراتر از چندجمله‌ای هستند. اینکه آیا این مسائل اصلاً قابل بررسی در زمان اجرای چندجمله‌ای هستند یا خیر از بزرگترین مسائل در علم کامپیوتر است. اگر یک الگوریتم زمان اجرای چندجمله‌ای حتی برای یکی از این مسائل پیدا شود آنگاه برای تمام این مسائل الگوریتمی با زمان اجرای چندجمله‌ای پیدا خواهد شد. بنا بر این علت و همچنین این علت که تا کنون تمامی تحقیقات برای بدست آوردن چنین الگوریتمی برای هر یک از این مسائل به شکست منجر شده‌است، هنگامیکه ثابت می‌شود مسئله‌ای NP-Complete است پیدا شدن الگوریتمی با زمان اجرای چندجمله‌ای برای آن بعید به نظر می‌رسد. رابطه با سایر کلاسها NP شامل تمام مسائل P می‌شود زیرا هر کس می‌تواند با نادیده گرفتن شواهد حل مسئله هر نمونه از این مسائل را حل کند. برای نشان دادن این کافی است یک ماشین PSPACE درست کنیم که بر روی تمام رشته‌های گواه گردش کند و هر کدام را به یک بررسی‌کننده زمان اجرای چندجمله‌ای ارائه دهد. | ## بخش 3: NP (پیچیدگی) | از آنجا که این ماشین تنها می‌تواند بیت‌هایی با تعداد چندجمله‌ای را بخواند نمی‌تواند در فضاهایی فراتر از چندجمله‌ای به کار رود و نمی‌تواند بررسی کننده‌ای را بپذیرد که زمان اجرایی فراتر از چندجمله‌ای نیاز دارد (بنابر این ما نیازی نداریم تا گواه‌هایی را بررسی کنیم که زمان اجرای طولانی تری دارند) NP همچنین در مجموعه EXPTIME موجود است. CO-NP شامل آن سری مسائلی است که گواه‌های ساده‌ای برای نادرست بودن دارند که بعضی اوقات مثال نقض نامیده می‌شود. برای مثال تست اول بودن یک عدد صحیح در حوزهٔ CO-NP قرار می‌گیرد زیرا می‌توان غیر اول بودن یک عدد را به راحتی با پیدا کردن یک عامل آن مشخص کرد. اگر ما به بررسی‌کننده توانایی احتمالی بودن را نسبت دهیم (بطور خاص ماشین BPP) به کلاس MA می‌رسیم که قابل حل با قراداد آرتور- مرلین بدون برقراری ارتباط بین آرتور و مرلین است. NP شامل زبان‌های مرتبهٔ دوم منطق است که استفاده از متغیرهای جهانی را بر روی روابط؛ مجموعه‌ها و توابع مانع شده باشند. NP را می‌توان به چشم یک سیستم اثبات متقابل بسیار ساده نگاه کرد که اثبات‌کننده یک شاهد اثبات ارائه می‌کند و بررسی‌کننده در یک زمان اجرای چندجمله‌ای به صورت جبری آن را بررسی کند. این اثبات کامل است زیرا یک رشتهٔ اثبات صحیح پذیرفته می‌شود و مانع است زیرا بررسی‌کننده پذیرفته نمی‌شود اگر رشتهٔ اثبات صحیحی وجود نداشته باشد. یک نتیجه‌ای مهم نظریه پیچیدگی اینست که NP می‌تواند به صورت مسائلی دسته‌بندی شود که با اثبات‌های مبتنی بر بررسی احتمال قابل بررسی باشند. به‌صورتی که بررسی‌کننده از تعداد (O(log n بیت تصادفی استفاده می‌کند و در هر مرحله تعداد ثابتی از بیت‌ها را به عنوان رشتهٔ اثبات (کلاس PCP (logn,1 ارزیابی می‌کند. به صورت غیررسمی تر می‌توان گفت بررسی کنندهٔ NP که در قبل معرفی شد را می‌توان با بررسی کننده‌ای عوض کرد که با تکنیک «بررسی نقطه به نقطه» چندین نقطه در رشتهٔ اثبات را بررسی می‌کند؛ و به این ترتیب می‌توان با چند محاسبهٔ ساده می‌توان جواب درست را با احتمال بالا بدست آورد. با این روش می‌توان نتایج زیادی دربارهٔ سختی مسائل بهینه‌سازی را اثبات کرد مثال مدل تصمیم‌گیری مسئله فروشنده دوره‌گرد NP به حساب می‌آید. مسئله این است که آیا مسیری وجود دارد که از همهٔ شهرها بگذرد و طول آن کمتر از K باشد. هر شهر تمام شهرهای همسایه را بررسی می‌کند تا هنگامیکه تمام شهرها را ملاقات کند و اگر به بن‌بست برسد بلافاصله متوقف می‌شود. می‌توان این طور فکر کرد که هر حدس یک کپی از ماشین تورینگ است که راه‌های ممکن را پیش رو می‌گیرد و اگر حداقل یک ماشین یک مسیر کوتاهتر از K پیدا کند آن ماشین ورودی را می‌پذیرد. (متناظرا این مسئله را می‌توان این طور در نظر گرفت که یک ماشین تورینگ وجود دارد که همواره جواب درست را حدس می‌زند). جستجوی دودویی بر روی فواصل ممکن می‌تواند این مسئلهٔ تصمیم‌گیری را به یک مسئلهٔ بهینه‌سازی تبدیل کند. مثال های دیگر: مسئله طولانی‌ترین مسیر بهینه‌سازی خطی عدد صحیح مسئلهٔ یافتن مجموعهٔ مستقل نتیجه‌گیری مسائل NP در زمان نمایی با توجه به مقدار ورودی اجرا می‌شوند. | ## جمع‌بندی | واژه "NP کامل " بدین معنی است که یک مسئله ارزش این را ندارد که سعی شود به صورت بهینه کامل حل شود.