Бывают такие проблемы, что даже при наличии мощной экзафлопсной машины, надежного программного обеспечения и безупречных людей для достижения успеха просто не хватает времени. Например, алгоритм поиска наибольшего числа в списке из N чисел имеет время работы, пропорциональное N. Алгоритм, который, скажем, вычисляет расстояния полета между N аэропортами на карте, имеет время работы, пропорциональное N в степени 2, или N в квадрате, поскольку для каждого аэропорта он должен определить расстояние до каждого из остальных.

Ученые-теоретики-компьютерщики классифицируют алгоритмы в зависимости от времени их выполнения, которое измеряется по количеству данных N, которыми алгоритмы манипулируют. Алгоритмы, время работы которых пропорционально N, возведенному в степень, называются «полиномиальными», или P. Если алгоритму, время выполнения которого пропорционально N, требуется секунда для выполнения вычислений, включающих 100 элементов, то есть N = 100, то алгоритм, время выполнения которого пропорционально N в кубе, занимает почти 3 ч.

Если ответ можно быстро проверить, то он относится к классу NP. Но алгоритм, время выполнения которого пропорционально 2 степени N (то есть экспоненциально по N), занял бы 300 квинтиллионов лет. Когда N появляется в показателе степени и ни один умный алгоритм не может свести выполнение к полиному по времени от N, это выражается в том, что проблема называется NP-полной. Классическим примером является обманчиво простая задача о коммивояжере, которая спрашивает: «При наличии списка городов и известных расстояний между каждой парой городов каков кратчайший возможный маршрут, который включает каждый город ровно один раз и приводит в исходный?»