روش‌های مختلفی برای حلّ سریع ولی نزدیک به بهینه برای یک مسألۀ NP-Hard وجود دارد:

  • راه حلّ تقریبی قابل اثبات(الگوریتم‌های تقریبی): که در آن یک الگوریتم سریع برای حلّ مسأله ارائه می‌شود ولی اثبات می‌شود که اندازۀ خروجی ضریبی از اندازۀ خروجی بهینۀ مسأله ‌است.
  • الگوریتم‌های مکاشفه‌ای: با این که الگوریتم‌هایی سریع هستند و به صورت تقریبی جواب را به دست می‌آورند، اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد. بسیاری از این الگوریتم‌ها به صورت تجربی آزمایش می‌شوند. برخی از این الگوریتم‌ها از «روش حریصانه» برای حل استفاده می‌کنند.

راه‌های معمول مقابله با چنین مسائلی عبارتند از:

  • طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
  • استفاده از «الگوریتم‌های مکاشفه‌ای»[1] که جواب‌هایی به‌دست می‌دهد که احتمالاً درست هستند.
  • پیدا کردن زیرمسأله‌هایی از مسأله، یعنی تقسیم مسأله به مسأله‌های کوچکتر.

دو مسألۀ زیر جزءِ مسائل NP-Hard می‌باشند:

  • مسئله فروشنده دوره‌گرد
  • مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل)[2][17]

اما مسائل مهم زیادی نیز وجود دارند که یافتن راه‌حل در آنها بسیار دشوار است. اما اگر راه‌حل را داشته باشیم، بررسی آن آسان می‌شود. این واقعیت منجر به مسائل NP-Complete problems شد.NP معرف Nondeterministic (چند جمله‌ای‌های غیرجبری) و به این معناست که امکان این وجود که راه‌حل را حدس زد و سپس آن را بررسی کرد.

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

یکی از ویژگی‌های مسائل NP آن است که یک الگوریتم ساده را (که ممکن است در نگاه اول بدیهی به نظر برسد) می‌توان برای یافتن راه‌حل‌های مفید به کار برد. اما بطور کلی، این روش، روش‌های ممکن زیادی را فراهم می‌کند و بررسی کردن تمام راه‌حل‌ها، فرآیند بسیار کندی خواهد بود.

امروزه، هیچکس نمی‌داند که آیا الگوریتم سریعتری برای یافتن جواب دقیق در مسائل NP وجود دارد یا خیر. و یافتن چنین الگوریتمی وظیفه مهمی است که به عهده محققان می‌باشد. امروزه اکثر مردم تصور می‌کنند که چنین الگوریتمی وجود ندارد و بنابراین به دنبال روش دیگری (جایگزین) هستند. و نمونه‌ای از روش جایگزین، الگوریتم ژنتیکی است. [13]

[1] Heuristic

[2] Maximum Clique Problem