تعریف np و np کامل

ممکن است شنیده باشید که فلان مساله np است و نمی توان آن را حل کرد. اما واقعا یعنی چه؟ و چرا نمی توان آن را حل کرد؟ در این فصل به بررسی این مسائل می پردازیم.

هدف از این فصل، تعیین تکلیف مسائلی از گراف است که به ارائه الگوریتمی برای آن ها نپرداختیم. این فصل، عدم موفقیت ما برای ارائه الگوریتم پرکتیکال برای این مسائل را توجیه می کند.

این مبحث، یکی از مباحث علوم نظری کامپیوتر است. اگر چه خواندن این فصل به طور مستقیم کمکی به موفقیت شما در آزمون های المپیاد کامپیوتر نخواهد کرد، اما خواندن آن به دلایل زیر توصیه می شود:

  • این مبحث یکی از جالب ترین مباحث علوم نظری کامپیوتر است و شما که علاقه مند به المپیاد کامپیوتر هستید قطعا از آن لذت خواهید برد.
  • خواندن این مبحث به شما کمک می کند تا از باور های غلط رایج در میان دانش آموزان درباره مسائل np دور بمانید.
  • خواندن این مبحث به شما کمک می کند که راحت تر مسائل np را تشخیص دهید و در آزمون به حل آن ها نپردازید.

مسائل تصمیم

مسائل تصمیم، مسائلی هستند که پاسخ آن ها تنها یک بیت است. یعنی پاسخ آن ها بله یا خیر است. مثلا مساله یک عدد را تجزیه کنید یک مساله تصمیم نیست اما یک عدد اول است یا خیر یک مساله تصمیم است.

عموما برای مسائل، یک مساله تصمیم وجود دارد که می توان با آن، مساله اصلی را حل کرد. مثلا مساله کوچک ترین عامل اول این عدد، بزرگ تر از k است یا خیر می تواند به کمک یک جستجوی دو دویی مساله تجزیه را حل کند. در حالت کلی، مساله تصمیم آیا بیت کا ام خروجی ۱ است، می تواند مساله اصلی را حل کند.

در این بخش ما با مسائل تصمیم سر و کار داریم، اما از نتیجه می توان به طور گسترده در مسائل دیگر نیز استفاده کرد.

کلاس P

مسائل کلاس P دسته ای از مسائل تصمیم هستند که الگوریتمی وجود دارد که می تواند در \(O(|s|^k)\) نتیجه را معین کند. در این جا \(s\) رشته ورودی، \(|s|\) طول رشته ورودی و \(k\) یک عدد ثابت مستقل از ورودی است. به عبارت دیگر، مسائلی که در زمان چند جمله ای بر حسب طول ورودی حل می شوند، در این کلاس هستند. توجه کنید که طول ورودی همیشه پارامتری نیست که ما برحسب آن پیچیدگی الگوریتم را تحلیل می کنیم، مثلا مساله تصمیم تجزیه یک عدد، یعنی آیا عدد \(n\) عامل اولی کوچک تر از \(k\) دارد یا خیر، الگوریتمی با پیچیدگی زمانی \(O(\sqrt{n})\) یا همان \(n^{\frac{1}{2}}\) دارد اما این مساله در کلاس P قرار ندارد. زیرا طول ورودی از \(O(lg(n))\) بوده است و یعنی الگوریتم ما بر حسب طول ورودی، چند جمله ای نبوده است.

کلاس NP

این مسائل، دسته ای از مسائل هستند که لزوما یک راه حل چند جمله ای ندارند، اما یک تایید کننده چند جمله ای دارند.

تایید کننده

تایید کننده یک مساله، خود یک مساله تصمیم است که ورودی مساله اصلی را به همراه یک رشته کمکی (که یک جواب یا اثبات خوانده می شود) می گیرد و تعیین می کند که آیا این جواب درستی برای مساله است یا نه. اگر یک رشته کمکی وجود داشته باشد که تایید کننده آن را تایید کند، یعنی جواب مساله اصلی مثبت بوده است و اگر جواب مساله اصلی منفی باشد، هیچ رشته ای وجود ندارد که تایید کننده آن را تایید کند.

به عبارت دقیق تر، اگر مساله اصلی را با \(X\) نشان دهیم که \(X(s)\) یا تایید و یا رد است، به یک مساله مانند \(C(s,t)\) یک تایید کننده برای مساله ایکس می گوییم اگر و تنها اگر دو شرط زیر برقرار باشد:

  • اگر \(X(s) = 0\) باشد آن گاه به ازای هر رشته ممکن t \(C(s,t) = 0\) است.
  • اگر \(X(s) = 1\) باشد آن گاه حداقل یک رشته وجود دارد که \(C(s,t) = 1\) باشد.

تعریف

حال به تعریف کلاس NP باز می گردیم. یک مساله عضو این کلاس است، اگر و تنها اگر یک تایید کننده داشته باشد که در زمان چند جمله ای به نتیجه برسد و هم چنین اگر جواب مساله اصلی مثبت است، یک رشته کمکی با طول چند جمله ای نسبت به ورودی وجود داشته باشد که تایید کننده آن را تایید کند.

مثال

طیف گسترده ای از مسائل در این کلاس قرار دارد. مثلا مساله این که آیا گراف دور همیلتونی دارد یا خیر را در نظر بگیرید. یک تایید کننده، می تواند جایگشتی از رئوس را در ورودی بگیرد و بررسی کند که آیا هر عضو این جایگشت به عضو بعدی اش یال دارد یا خیر. اگر جواب مساله اصلی منفی باشد هیچ جایگشتی وجود ندارد و اگر مثبت باشد جایگشتی وجود دارد که طول آن از گراف اصلی کمتر است و تایید کننده می تواند در زمان خطی، این بررسی را انجام دهد. پس مساله دور همیلتونی یک مساله در کلاس NP است.

مساله تصمیم متناظر تجزیه اعداد نیز یک مساله NP است. یک تایید کننده می تواند یک عدد کوچکتر از k را ورودی بگیرد و تشخیص دهد که آیا ورودی به این عدد بخش پذیر است یا نه. این تشخیص می تواند در زمان چند جمله ای تقسیم را انجام دهد (با کمک الگوریتمی که در دبستان خواندیم) و طول اثبات (همان عدد کوچکتر از k) از طول ورودی کمتر است بنابراین این مساله نیز در کلاس NP قرار دارد.

کاهیدن چند جمله ای

تعریف می کنیم مساله A به مساله B در زمان چند جمله ای کاهیده می شود، اگر و تنها اگر بتوان به کمک یک الگوریتم و یک ماشین پیشگوی مساله B مساله A را در زمان چند جمله ای حل کرد. کاهیدن از این جهت مورد توجه است که اگر A به B کاهیده شود و B در زمان چند جمله ای حل شود، A نیز در زمان چند جمله ای حل می شود.

مسائل NP سخت و NP کامل

به یک مساله NP سخت می گوییم اگر و تنها اگر هر مساله در کلاس NP را بتوان در زمان چند جمله ای به این مساله کاهید. اگر یک مساله NP سخت خود در کلاس NP باشد، به آن NP کامل گفته می شود. شاید عجیب به نظر برسد که همه مسائل که گستره و تنوع عظیمی دارند را به یک مساله کاهید، اما در ادامه این فصل با مسائل NP سخت و NP کامل زیادی آشنا می شوید.

P=NP

این مساله بزرگترین مساله باز در کل علوم کامپیوتر است. این مساله بیان می کند که آیا همه مسائل کلاس NP در زمان چند جمله ای حل می شوند یا خیر؟ این مساله معادل این است که یکی از مسائل NP سخت را بتوان در زمان چند جمله ای حل کرد.

جواب مثبت به این مساله، تمام الگوریتم های رمز نگاری را می شکند و پتانسیل فروپاشی اقتصاد را دارد. از طرفی دیگر، مسائل محاسباتی که اکنون میلیارد ها سال طول می کشند را در زمان کوتاهی محاسبه می کند. می تواند کلید حل سرطان را ها پیدا کند و ...

جواب منفی به این مساله اگرچه کاربرد عملی ندارد و باور عمومی این است که جواب منفی است، ولی یک پیشرفت شگرف در علوم نظری کامپیوتر است. برای اثبات این مساله، یک میلیون دلار جایزه در نظر گرفته شده است.