مسائل رام نشدني

راه حلهای ارئه شده برای مسائل در حالت کلی غالبا به دو صورت ظاهر می شوند.

 1. الگوریتمهایی که پیچیدگی زمانی آنها حداکثر چند جمله ای می باشد.

 2. مسائلی که لگوریتمهای ارائه شده برای آنها از درجه نمایی می باشد.

دسته دوم در عمل کاربرد خاصی ندارند .

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

نظریه NP

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

هر مسئله ای که جواب آن بلی یا خیر باشد مسئله تصمیم گیری است .

کلاسهای NP-hard , NP-complete , NP , P از مسائل ، همه در چارچوب مسائل تصمیم گیری تعریف و بررسی می شوند .