Золотой билет. P, NP и границы возможного

«Пути, деревья и цветы» дали нам не только эффективный способ решения задачи о паросочетаниях для случая произвольной схемы. В группе из 100 человек алгоритм Эдмондса находит максимальное паросочетание примерно за 100⁴, т. е. 100000000 (сто миллионов) шагов, что для современного компьютера сущий пустяк. Методичный перебор всех возможных сочетаний вылился бы примерно в два квинвигинтиллиона шагов, а один квинвигинтиллион – это, между прочим, единица и 78 нулей! В работе Эдмондса есть довольно длинное отступление на тему эффективных алгоритмов. Понимая, что для такого, в сущности, интуитивного понятия, как эффективность, подобрать полноценное формальное определение очень сложно, Эдмондс все-таки предлагает некий критерий. Он называет алгоритм эффективным, если тот находит решение за «алгебраическое» время, т. е. время, «алгебраически» зависящее от размера входных данных. Для 100 человек это может быть, к примеру, 100⁴, 100² или 100¹². В дальнейшем класс задач, для которых существуют такие алгоритмы, получил обозначение «P» – от слова «полиномиальный», заменившего эдмондсовское понятие «алгебраический». Таким образом, класс P представляет собой все многообразие задач, которые можно решить относительно быстро. Ну что ж – в споре «P против NP» мы выслушали мнение первой стороны.