Нам нужно разделить алгоритмы и задачи. Мы пишем алгоритмы для решения проблем, и они масштабируются определенным образом. Хотя это упрощение, давайте обозначим алгоритм буквой «P», если масштабирование достаточно хорошее, и «NP», если это не так.
Полезно знать о проблемах, которые мы пытаемся решить, а не об алгоритмах, которые мы используем для их решения. Итак, мы скажем, что все задачи, которые имеют алгоритм масштабирования, находятся "в P". А те, у которых алгоритм плохого масштабирования, находятся "в NP".
Это означает, что множество простых задач тоже «в NP», потому что мы можем писать плохие алгоритмы для решения простых задач. Было бы хорошо узнать, какие проблемы в NP являются действительно сложными, но мы не просто хотим сказать: «Это те, для которых мы не нашли хорошего алгоритма». В конце концов, я мог бы столкнуться с проблемой (назовите это X), которая, я думаю, нуждается в супер-удивительном алгоритме. Я говорю миру, что лучший алгоритм, который я мог бы придумать для решения X, плохо масштабируется, и поэтому я думаю, что X - действительно сложная проблема. Но завтра, может быть, кто-нибудь умнее меня придумает алгоритм, который решает X и находится в P. Так что это не очень хорошее определение сложных проблем.
Тем не менее, в NP много проблем, для которых никто не знает хорошего алгоритма. Так что, если бы я мог доказать , что X представляет собой определенную проблему, такую, где хороший алгоритм для решения X мог бы также , каким-то окольным путем, дать хороший алгоритм для каждая другая проблема в NP. Что ж, теперь люди могут быть немного более убеждены в том, что X - действительно сложная проблема. И в этом случае мы называем X NP-Complete.