P در برابر NP

شرح دقیق مسئله

کلاس � شامل مسائلی است که ماشین قطعی در زمان چندجمله‌ای حلشان می‌کند. کلاس � شامل مسائلی است که اگر یک شاهد یا جواب پیشنهادی � داشته باشیم، می‌توانیم در زمان چندجمله‌ای بررسی کنیم که آیا واقعاً جواب است یا نه: پس مسئلهٔ اصلی این است: نمونهٔ شهودی، Hamiltonian Path است: اگر مسیر را به ما بدهند، بررسی درستی آن آسان است؛ اما یافتن چنین مسیری ممکن است بسیار دشوار باشد. این پرسش از تاریخ منطق، Entscheidungsproblem، مفهوم الگوریتم کارآمد و کارهای Edmonds، Cook و Karp شکل گرفت. Sipser این تاریخ را به‌تفصیل دنبال می‌کند و مسئله را نسخه‌ای متناهی‌تر از دغدغهٔ Entscheidungsproblem می‌داند. � Princeton CS +1 نقطهٔ انفجاری، قضیهٔ Cook–Levin است: SAT در � کامل است؛ بنابراین اگر SAT در � باشد، آنگاه: در طرف مقابل، برای اثبات � باید یک مسئلهٔ مشخص در � پیدا کنیم که هیچ الگوریتم چندجمله‌ای برای آن وجود ندارد؛ و این مستلزم lower bound بسیار قوی است. از نظر بنیادی، این مسئله دربارهٔ فاصلهٔ میان سه مفهوم است: پیدا کردن جواب بررسی جواب وجود جواب