آیا NP=P ؟

آیا NP=P ؟

برای نشون دادن معتبر بودن یک استدلال، مثلا Γ در منطق گزاره ها میتونیم نشون بدیم که این گزاره یک توتولوژیه. برای اینکار اگر عبارت ما دارای n متغیر بود باید 2 به توان n حالت رو چک کنیم ، پس این مساله در زمان چند جمله ای(polynominal) قابل حل نیست این مساله رو با TAUT نشون میدیم، اما اگر در مساله ای حد اقل یک مقدار دهی برای متغیر ها پیدا کنم که Γ در اون حالت درست(T) باشه نشون دهنده اینه که Γ یک تناقض منطقی(contradiction) نیست یا به عبارتی مجموعه Γ سازگارند، این مساله رو با SAT نشون میدیم یعنی حد اقل یک مقداردهی وجود داره که شرایط رو ارضا(satisfy) میکنه. اما ما میتونیم مساله صحت استدلال رو که با TAUT طرح کردیم به فورم SAT درش بیاریم با این حال که اگر بتونیم حد اقل یک مقدار دهی رو برای Γ~ پیدا کنیم که مقدارش درست باشه یعنی Γ~  نمیتونه تناقش باشه، پس در نتیجه Γ یک توتولوژی نیست پس استدلالمون معتبر نیست. در مساله اولی ما مجبور بودیم 2 به توان n حالت رو برای توتولوژی بودن عبارت چک کنیم یعنی یک مرتبه نمایی(ٍExponential)، اما در مساله دومی اگر بتونیم در همون ابتدا یک مقدار دهی درست پیدا کنیم نیاز نیست این پردازش نمایی رو تا اخر انجام بدیم پس مساله میتونه در زمان چند جمله ای حل بشه، فقط ماشین ما باید حدس درست و محتملی بزنه. هر چند اگر مساله ما هیچ مقدار دهی صحیحی نداشته باشه باز مجبوریم زمان نمایی رو بپیماییم. چنین ماشینی رو میگیم نان دترمنستیک(non-deterministic)  یا غیر قطعی. چنین مسائلی رو، یعنی مسائلی که در زمان چند جمله ای در ماشین نان دترمنستیک قابل حل اند رو NP مینامیم. این سوال مطرح میشه که آیا NP=P ? یعنی همه مسائل NP رو میشه دریک ماشین دترمنستیک در زمان چند جمله ای حل کرد؟ بنظر میرسه اثبات NP=P خیلی مشکل تر از این باشه که نشون بدیم آیا SAT رو میشه تو زمان P حل کرد. اما  آقای استیون کوک(Stephen Cook)  نشون داد که اگر بتونیم اثبات کنیم که SAT عضو P هست مساله NP=P رو حل کردیم چون SAT جز سخترین مسائل NP ـه. اصطلاحا جز مسائل NP-Complete محسوب میشه. مسائل NP-Complete زیادی در زمینه های مختلف از جمله نظریه اعداد، بهینه سازی و رمزنگاری و منطق کشف شده، پس حل کردن هر کدوم از اینها کلیدی برای دانستن مسائله اصلی محسوب میشه.