مرجع کلمات و اصطلاحات اختصاری

در نظریه پیچیدگی محاسباتی NP یکی از بنیادی‌ترین کلاس‌ها است. NP مخفف عبارت “non deterministic polynomial” است که به زمان اجرای آن اشاره دارد.
NP مجموعهٔ کلیه مسائل تصمیم گیری است که پیدا کردن جواب بله برای آنها شامل اثبات ساده ای است که جواب حقیقتاَ باید بله باشد. بطور دقیق تر این اثبات‌های ساده باید قابل بررسی در یک زمان اجرای چند جمله ای در یک ماشین تورینگ جبری باشد. در مقابل این تعریف NP مجموعه مسائل تصمیم گیری نامیده می‌شود که در یک زمان اجرای چند جمله ای در یک ماشین تورینگ غیر جبری قابل بررسی باشند. کلاس پیچیدگی P یکی از اعضای NP است اما NP شامل کلاس‌های مهم دیگری نیز هست. که پیچیده‌ترین آنها NP-Complete است بطوریکه برای آنها هیچ الگوریتم شناخته شده قابل اجرا در زمان چند جمله ای وجود ندارد .
مهمترین سوالی که اکنون برای این کلاسها در این نظریه وجود دارد این است که آیا P=NP ؟ این سوال می پرسد که آیا چنین الگوریتمی واقعا برای مسائل NP-Complete و در کل NP وجود دارد یا خیر. این باور گسترده وجود دارد که این تساوی نمی تواند درست باشد.

ارسال نظر