Золотой билет. P, NP и границы возможного - Фотноу Лэнс

У Дэвида нет пары, однако он дружит с Фелисити, которую мы сочетали с Бобом. Боб дружит с Гейл, но чету они не образуют. Гейл соединена с Карлом, а Карл дружит с одинокой Хелен. Разлучим Боба с Фелисити и Карла с Гейл и составим новые связи. Теперь пара есть у всех!

Вернемся к рис. 3.3. Цепь из чередующихся сплошных и пунктирных линий, первый и последний элемент которой не имеет пары, т. е. не принадлежит паросочетанию, называется увеличивающим путем. При наличии увеличивающего пути мы всегда можем увеличить наше паросочетание. В 1957 году математик Клод Берж показал, что для любого паросочетания, не являющегося максимальным, существует увеличивающий путь. Программисты Королевского технологического реализовали алгоритм нахождения увеличивающих путей, основанный на методе последовательного поиска, и в результате смогли подобрать пару для 98 процентов участников эксперимента.

Вскоре после описанных событий Королевский верховный суд вынес постановление, разрешающее однополые браки. На сайте института тут же вывесили объявление о наборе волонтеров любых сексуальных ориентаций. Схемы заметно усложнились; появились даже любовные треугольники, которые к тому же частично пересекались друг с другом (см. ниже).

Простыми методами находить увеличивающие пути уже не получалось, и исследователи обратились к трудам Джека Эдмондса. В 1965 году Эдмондс написал работу с изящным названием «Пути, деревья и цветы», в которой представил усложненный алгоритм поиска увеличивающих путей, подходящий для совершенно произвольных схем. Реализовав метод Эдмондса, специалисты института сумели подобрать пару для 97 процентов участников второго эксперимента.

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

Конец ознакомительного фрагмента.