فرق کلاس P و NP و NP-Complete و NP-Hard به زبون ساده چیه؟!

کلاس P

هر مسئله‌ای که بتوان در زمان چندجمله‌ای حل کرد، به کلاس P تعلق دارد. پس مرتب‌سازی سریع مسئله‌ایست در کلاس P چون زمانش حداکثر مربعی است.

کلاس NP

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

کلاس NP-Complete

می‌بینیم که دو دسته مسائل در کلاس NP هست که یکی سخت‌تر از دیگری است. دسته سخت‌تر را مسائل NP-Complete می‌گویند. یعنی پیدا کردن تور بهینه NP-Complete است ولی مرتب‌سازی سریع فقط NP است و نیز P.

کلاس Np-Hard

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

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

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

منبع

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