NP چیست + سایر انواع کلاس های پیچیدگی در نظریه محاسبات

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

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

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

فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity در فرادرس

کلیک کنید

انواع کلاس های پیچیدگی محاسباتی

در این نوشتار به معرفی و شرح انواع کلاس‌های پیچیدگی زیر پرداخته شده است.

• کلاس P
• کلاس NP
• CoNP
• «NP سخت» (NP Hard)
• «NP کامل» (NP Complete)

در ادامه به معرفی هر یک از این انواع کلاس‌های پیچیدگی محاسباتی پرداخته شده است.

کلاس P در پیچیدگی محاسباتی

P اختصار عبارت «Polynomial Time» به معنی «زمان چند‌جمله‌ای» است. کلاس P مجموعه‌ای از مسائل تصمیم (مسائل با جواب بله یا خیر) است که توسط ماشین قطعی و در زمان چند‌جمله‌ای قابل حل است.

فیلم آموزش طراحی الگوریتم در فرادرس

کلیک کنید

ویژگی های کلاس P در پیچیدگی محاسباتی

در ادامه برخی از ویژگی‌های اساسی کلاس P در پیچیدگی محاسباتی فهرست شده‌اند.

1. یافتن راه‌حل برای مسائل P آسان است.
2. مسائل P اغلب قابل‌حل و «رام‌پذیر» (Tractable) هستند. مسئله‌ رام‌پذیر یعنی مسئله‌ای که هم به صورت نظری و هم به صورت عملیاتی قابل حل باشد. مسئله‌ غیر رام‌پذیر یعنی مسئله‌ای که در تئوری قابل‌حل، اما در عمل غیر قابل‌حل باشد.
3. کلاس P شامل بسیاری از مسائل طبیعی از جمله موارد زیر است:
   • محاسبه بزرگترین مقسوم علیه مشترک
   • یافتن حداکثر تطابق
   • نسخه‌های تصمیم برنامه‌ریزی خطی

فیلم آموزش هوش مصنوعی – مقدماتی در فرادرس

کلیک کنید

کلاس NP چیست ؟

NP اختصار عبارت «Non-Deterministic Polynomial Time» به معنی «زمان چند‌جمله‌ای غیرقطعی» است. کلاس NP مجموعه‌ای از مسائل تصمیم‌گیری به حساب می‌آید که می‌تواند به وسیله ماشین غیرقطعی و در زمان چند‌جمله‌ای حل شود.

ویژگی های کلاس NP

1. یافتن جواب برای مسائل کلاس NP سخت است، زیرا توسط ماشین غیرقطعی حل می‌شوند، اما جواب‌ها به سادگی قابل تأیید هستند.
2. مسائل NP را می‌توان توسط ماشین تورینگ در زمان چند‌جمله‌ای تایید کرد.

مثالی برای درک بهتر کلاس NP

برای درک بهتر کلاس NP مثالی را در نظر می‌گیریم. فرض کنید شرکتی وجود دارد که مجموعاً هزار کارمند دارد. شناسه کارمندان منحصر به فرد است و 200 اتاق برای آن‌ها در دسترس است. بنابراین کارمندان بایستی در ۲۰۰ اتاق توزیع شوند، اما مدیر عامل شرکت اطلاعات برخی از کارمندان را دارد که به دلایل شخصی نمی‌توانند در یک اتاق کار کنند.

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

این مسئله نشان می‌دهد که اگر کسی راه حل مسئله را ارائه دهد، می‌توانیم صحت راه‌حل را در زمان چند‌جمله‌ای بررسی کنیم. بنابراین برای مسئله کلاس NP ، تائید صحت پاسخ در زمان چند‌جمله‌ای امکان‌پذیر است و می‌تواند در عمل محاسبه شود. این کلاس شامل بسیاری از مسائل از جمله موارد زیر است:

• مسئله رضایتمندی بولی (SAT)
• مسئله مسیر همیلتونی
• رنگ آمیزی گراف

معرفی فیلم های آموزش ساختمان داده و طراحی الگوریتم

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

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

• برای شروع یادگیری ساختمان داده و طراحی الگوریتم + اینجا کلیک کنید.

کلاس Co-NP در پیچیدگی محاسباتی

Co-NP اختصار عبارت «Complement of NP Class» به معنی «مکمل کلاس NP» است. به این معنی که اگر پاسخ یک مسئله در Co-NP «خیر» باشد، بنابراین اثباتی وجود دارد که می‌توان آن را در زمان چند‌جمله‌ای بررسی کرد.

ویژگی های کلاس Co-NP چیست ؟

اگر یک مسئله X در کلاس NP قرار داشته باشد، آنگاه مکمل آن، 'X، در کلاس CoNP قرار خواهد داشت. برای یک مسئله NP و ConNP، نیازی به تأیید همه پاسخ‌ها به طور همزمان در زمان چندجمله‌ای نیست، صرفا باید پاسخی معین یعنی «بله» یا «خیر» در زمان چندجمله‌ای تائید شود. برخی از مسائل Co-NP عبارتند از:

• بررسی عدد اول
• تجزیه اعداد صحیح به اعداد اول (Integer Factorization)

کلاس NP Hard چیست ؟

مسئله NP Hard حداقل به سختی سخت‌ترین مسئله در NP است. کلاس NP به گونه‌ای است که هر مسئله در NP به NP Hard قابل تبدیل (کاهش) است.

ویژگی های کلاس NP Hard چیست ؟

• همه‌ی مسائل NP Hard در کلاس NP قرار ندارند.
• بررسی مسئله NP Hard زمان زیادی می‌برد. این بدان معنی است که اگر جوابی برای یک مسئله NP Hard ارائه شود، بررسی درست یا نادرستی آن زمان زیادی طول می‌‌کشد.
• اگر مسئله L واقع در کلاس NP را بتوان در زمان چند‌جمله‌ای به مسئله A تبدیل کرد (تقلیل و کاهش داد)ُ، آنگاه مسئله A یک مسئله NP Hard به حساب می‌آید.

برخی از نمونه‌های مسائل در کلاس NP Hard عبارتند از:

• مسئله توقف (Halting problem)
• فرمول‌ بولی کمی واقعی (True Quantified Boolean Formula)
• دور هامیلتونی در گراف جهت‌دار

کلاس NP Complete چیست ؟

یک مسئله NP Complete است اگر هم NP و هم NP Hard باشد. مسائل NP Complete مسائل سخت در NP به حساب می‌آیند.

ویژگی های کلاس NP Complete چیست ؟

• مسائل NP Complete خاص هستند، زیرا هر مسئله‌ای در کلاس NP می‌تواند در زمان چند جمله‌ ای به مسائل NP Complete تبدیل شود (کاهش یابد).
• اگر بتوان یک مسئله NP Complete را در زمان چند‌جمله‌ای حل کرد، آنگاه می‌توان همه مسئله NP را نیز در زمان چند‌جمله‌ای حل کرد.

برخی از نمونه‌های مسائل در NP Complete عبارتند از:

• نسخه تصمیم مسئله کوله‌ پشتی
• مسئله دور هامیلتونی
• «رضایت‌پذیری» (Satisfiability)
• «پوشش گره‌ای» (Vertex Cover)

فیلم آموزش مسائل p و np در طراحی الگوریتم (رایگان) در فرادرس

کلیک کنید

جدول مقایسه انواع کلاس های پیچیدگی محاسباتی مسائل

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

سوالات رایج پیرامون پرسش NP چیست

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

NP مخفف چیست ؟

کوته‌نوشت NP مخفف عبارت «Nondeterministic Polynomial» و به معنی «چند‌جمله‌ای غیر قطعی» است. به بیان دقیق‌تر، NP به عبارت «Nondeterministic Polynomial Time» یعنی «زمان چند‌جمله‌ای غیر قطعی» اشاره دارد. این اصطلاح در حوزه نظریه پیچیدگی محاسبات مطرح می‌شود.

چرا حل برخی مسائل NP سخت است؟

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

آیا مسائل NP Hard قابل حل هستند؟

مسائل NP Hard (مثلا X) را می توان حل کرد اگر و تنها در صورتی که یک مسئله NP Complete (مثلا Y) وجود داشته باشد که بتواند در زمان چند‌جمله‌ای به X قابل کاهش باشد. مسائل NP Complete را می‌توان با یک الگوریتم غیر قطعی/ ماشین تورینگ در زمان چند‌جمله‌ای حل کرد.

چگونه می‌توان ثابت کرد که یک مسئله از نوع NP Hard است؟

برای اثبات اینکه مسئله A از نوع NP Hard است، می‌توان یک «مسئله NP Hard معروف» را به A تقلیل داد.

آیا همه مسائل NP Hard قابل کاهش به یکدیگر هستند؟

بله، هر مسئله NP را می‌توان در زمان چند‌جمله‌ای به یک مسئله NP Complete کاهش داد. از آنجایی که مسائل NP Complete زیرمجموعه‌ی مسائل NP هستند، همه مسائل NP Complete را می توان در زمان چند‌جمله‌ای به یکدیگر تقلیل داد.

آیا مسئله NP-hard می تواند در کلاس P واقع شده باشد؟

خیر، اگر مسئله‌ای NP-Complete باشد، در زمان چند‌جمله‌ای قابل حل نیست مگر اینکه P=NP که هنوز ثابت نشده است. علاوه بر این، اگر یک مسئله NP-hard وجود داشته باشد که در زمان چند جمله‌ای قابل حل باشد، آنگاه (با کاهش) می‌توان از آن برای حل هر مسئله دیگری در NP استفاده کرد، که این موضوع نشان‌دهنده P=NP است.

جمع‌بندی

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