Решение задачи и проверка полученного решения суть две разные и в равной степени важные процедуры.
Фишка в том, что время и трудоемкость проверяющей процедуры может сильно отличаться от времени и трудоемкости самого процесса решения. Проверить решение иногда очень просто. А вот решить задачу алгоритмически, то есть найти точный пошаговый способ решения, который определен однозначно, завершается за конечное время и выдает правильный результат, может оказаться сложно. В 1930 году австриец Карл Менгер придумал знаменитую задачу коммивояжера, которая относится как раз к этому типу NPполных задач. Смысл задачи в том, что условный коммивояжер должен найти самый короткий маршрут между несколькими городами так, чтобы через каждый город он проезжал только один раз и в итоге вернулся в исходную точку. Если речь идет о трех – пяти городах, это проще простого. Но по мере увеличения числа городов решение будет усложняться в геометрической прогрессии. Для пятнадцати городов существует сорок три миллиарда маршрутов, а для восемнадцати их уже сто семьдесят семь триллионов. При этом, если решение уже найдено, проверить его корректность легко – достаточно убедиться, что все заданные точки пройдены по одному разу.
И вот тут математики приходят в отчаяние. Задачато примитивная! Но единственный возможный способ ее решения – старый добрый перебор. Слишком простой и слишком трудоемкий.
Этот факт приводит математиков в ярость уже пятьдесят лет и наводит на мысль, что для облегчения судьбы коммивояжера существует – должен существовать! – другой алгоритм, куда более эффективный. Благодаря скромному коммивояжеру наука обогатилась несколькими новыми направлениями, но к лету 1988го основным методом решения этой задачи так и остался все тот же перебор.
Задачи, которые решаются относительно быстро, математики относят к классу сложности P. Задачи же, решение которых, как в случае коммивояжера, проверяется за полиномиальное время, относят к классу NP. Понятно, что все задачи класса P войдут и в класс NP. Вопрос в другом. Пример с коммивояжером показывает, что существуют задачи, которые принадлежат к классу NP (легко проверить), но не принадлежат к классу P (легко решить). Выходит, что, если никакого иного алгоритма решения задачи коммивояжера, кроме перебора, нет в природе, классы P и NP не равны. Но именно в этом математики и не уверены. Отсутствие иного алгоритма все еще не доказано. Если такой алгоритм будет найден, значит, задача коммивояжера не только легко проверяется, но и легко решается. И классы P и NP равны. Короткая статья Леонида Левина была как раз об этом.