تئوری NP کامل و مسائل کنترل پذیر و لجام گسیخته

مسائل موجود در علوم کامپیوتری را می توان به 2 دسته ی مسائل مهارشدنی و لجام گسیخته تقسیم کرد. مسائلی را مهارشدنی گویند، که اگر الگوریتمی با زمان اجرای کراندار چندجمله ای یافت شود که بتواند آن را حل کند. مراد از کران چند جمله ای این است که زمان اجرای الگوریتم در بدترین حالت به وسیله چند جمله ای (p(n) که n اندازه ورودی مسئله است، محدود شود. مسئله ای را لجام گسیخته گویند اگر مهارشدنی نباشد. الگوریتم هایی که این مسائل را حل می کنند در زمان چندجمله ای نمی باشند. یعنی برای بدترین حالت مسئله نمی توان چند جمله ای محدود کننده ای برای آن یافت. دسته بندی مسائل به این دو دسته به ما کمک می کند تا برای مسائلی که لجام گسیخته اند به دنبال راه حل چند جمله ای نباشیم. تمام الگوریتم ها برای این مسائل با ورودی های n بزرگ بسیار کند می باشند.