Золотой билет

Первая NP-полная задача

В 1970 году Том Хал, глава факультета информатики Университета Торонто, загорелся идеей переманить к себе Стивена Кука, которому не хотели давать постоянное место в Калифорнийском университете в Беркли. Зная любовь Кука к парусному спорту, Хал отвез его на озеро Онтарио: он хотел доказать, что в окрестностях Торонто ходить под парусом почти так же приятно, как и в заливе Сан-Франциско. Хитрость удалась, и осенью 1970 года Кук пополнил ряды специалистов Торонтского университета. Со стороны Хала это был блестящий ход, поскольку в скором времени Кук прославился на весь мир и стал самым известным канадским ученым в области теории вычислений.

Кук проводил исследования на стыке математической логики и теоретической информатики. Той осенью он отправил одну из своих работ на рассмотрение комиссии III Международного симпозиума по теории вычислений (Symposium on the Theory of Computing, сокращенно – STOC), проводимого Ассоциацией вычислительной техники. Симпозиум должен был состояться в мае 1971 года. В статье Кука содержались результаты, полученные им задолго до того и не вызвавшие в свое время ажиотажа. Исследования ученого заинтересовали комиссию, и заявку приняли. К началу конференции Кук почти все переделал; в новой статье, которая называлась The Complexity of Theorem-Proving Procedures, он впервые сформулировал проблему равенства классов P и NP и тем самым полностью изменил ход истории.

Чтобы лучше понять результаты Кука, вернемся к рассмотренной в предыдущей главе задаче о клике. Как вы помните, кликой мы называем группу жителей Королевства, в которой все дружат между собой. На представленной ниже схеме дружеских связей Алекс, Кэти и Эрик образуют клику, а вот Алекс, Дэвид и Эрик – нет, поскольку Алекс не дружит с Дэвидом.

Рис. 4.1. Задача о клике

Мы уже знаем, что в Королевстве есть полусекретное и довольно многочисленное сообщество «Альфа». «Альфовцы» утверждают, что все они дружат между собой, т. е. образуют гигантскую клику. Если это действительно так, то какие сведения можно почерпнуть о них из приведенной выше схемы? Теоретически каждый из пяти может входить в «Альфу». Нельзя исключить вероятность того, что Алекс или Дэвид входят в сообщество, однако они не могут быть там одновременно, поскольку дружбы между ними нет; значит, один из них в сообщество точно не входит. Запишем этот вывод в виде логического выражения:

Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе».

«ИЛИ» здесь не исключающее: возможен вариант, при котором ни Алекс, ни Дэвид не входят в сообщество. Алекс и Барбара тоже враждуют, а следовательно – не могут оба входить в «Альфу». Запишем и это:

Алекс не в «Альфе» ИЛИ Барбара не в «Альфе».

Оба утверждения должны выполняться одновременно, а значит, мы имеем:

(Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе»)

И

(Алекс не в «Альфе» ИЛИ Барбара не в «Альфе»).

Барбара и Дэвид – друзья, поэтому они вполне могут одновременно входить в «Альфу», и построенное нами выражение такой возможности не исключает. Проанализировав всю схему, мы в итоге получим следующее выражение:

(Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе») И (Алекс не в «Альфе» ИЛИ Барбара не в «Альфе») И (Дэвид не в «Альфе» ИЛИ Кэти не в «Альфе») И (Кэти не в «Альфе» ИЛИ Барбара не в «Альфе»).

Допустим, Алекс, Кэти и Эрик принадлежат сообществу, а Барбара и Дэвид – нет; тогда наше выражение истинно, так как в каждом условии «ИЛИ» упоминается кто-то, кто в «Альфу» не входит. Теперь предположим, что сообществу принадлежат Алекс, Дэвид и Эрик. Тогда условие (Алекс не в «Альфе» ИЛИ Дэвид не в «Альфе») не выполняется, поскольку и Алекс, и Дэвид входят в сообщество, а значит – ложно и все выражение.

Наше выражение будет истинно только в том случае, когда все «альфовцы» действительно дружат между собой; с помощью подобных выражений клики отлавливаются очень легко.

Аналогичную конструкцию можно составить и для всех 20 тысяч жителей Королевства. В результате получится огромное, содержащее несколько миллионов символов выражение – впрочем, не настолько длинное, чтобы не уместиться в компьютер. Для краткости обозначим его буквой Φ. Очевидно, что Φ будет истинно только тогда, когда «альфовцы» в самом деле образуют клику.

Через Ψ50 обозначим выражение, истинное в том случае, если в «Альфу» входят хотя бы 50 человек. Не будем углубляться в его структуру; достаточно будет сказать, что построить его можно тем же способом, каким первые цифровые компьютеры выполняли сложение чисел.

Соединим наши выражения в одно: (Ψ50 И Φ). Если члены сообщества образуют клику размером не меньше 50, то новое выражение примет значение «истина», и наоборот – если выражение истинно, то члены сообщества образуют клику размером не меньше 50.

Логическое выражение, проверяющее принадлежность к сообществу, называется выполнимым, если сообщество можно составить таким образом, что выражение примет значение «истина». Выражение (Ψ50 И Φ) выполнимо, когда в сообществе есть клика размера не меньше 50.

Предположим, у нас есть быстрый алгоритм, проверяющий выполнимость логического выражения. Подадим ему на вход выражение (Ψ50 И Φ); если алгоритм ответит «да», то в Королевстве существует клика размера 50, а если «нет» – то не существует. Таким образом, алгоритм решения задачи о выполнимости позволяет решить и задачу о клике.

То, чем мы сейчас тут занимались, называется процессом сведения одной задачи к другой. Сведение широко используется в теории сложности, и мы с вами только что свели проблему клики к проблеме выполнимости логического выражения, показав тем самым, что любой метод решения задачи о выполнимости можно применить и к задаче о клике. Появление эффективного алгоритма для задачи о выполнимости означало бы, что такой алгоритм существует и для задачи о клике; найти клику не труднее, чем определить условия выполнимости, и если задачу о выполнимости можно легко решить – значит, задача о клике тоже легко решаема. С другой стороны, если бы кому-то удалось доказать, что для задачи о клике эффективного алгоритма не существует, это означало бы, что его не существует и для задачи о выполнимости.

На самом деле к проблеме выполнимости, или SAT (от англ. satisfiability – выполнимость), сводится не одна лишь задача о клике, но и другие задачи класса NP, которые мы обсуждали ранее, включая задачу о коммивояжере, поиск гамильтонова пути, построение максимального разреза и раскраску карт. Стивен Кук доказал, что любая проблема из NP сводится к проблеме выполнимости. Решите проблему выполнимости – и у вас будет ключ ко всем проблемам из NP. Появление эффективного алгоритма для задачи о выполнимости будет означать, что такой алгоритм существует для всех задач, решение которых легко проверяется, а следовательно, P = NP. Создайте эффективный алгоритм решения проблемы SAT – и получите миллион долларов от Института Клэя!

Сама проблема SAT также принадлежит NP, поскольку для любого набора входных переменных истинность логического выражения проверяется относительно быстро. В классе NP эта задача является универсальной или, как еще говорят, самой трудной, или NP-полной. Доказать наличие эффективного алгоритма для ее решения значит доказать равенство P и NP.

Симпозиум проходил в городке Шейкер-Хайтс в штате Огайо, в отеле Somerset Inn, принадлежащем компании Stouffer. Стивен Кук выступил с докладом 4 мая 1971 года.

«Полученные результаты дают нам основания полагать, что проблема выполнимости – задача чрезвычайно любопытная, поскольку она, по всей видимости, не имеет эффективных методов решения. Думаю, стоит попытаться доказать данную гипотезу: в теории сложности это стало бы величайшим прорывом».

С того дня и ведет свою историю проблема равенства P и NP.

Двадцать плюс одна

Работу Кука оценили, однако ажиотаж вокруг нее поднялся не сразу. В те годы проблема выполнимости интересовала немногих, и никто еще толком не понимал смысл класса NP. Кук даже не придумал ему названия и пользовался выражением «недетерминированное полиномиальное время». Все изменилось, когда вслед за Куком свою работу опубликовал профессор Ричард Карп из Калифорнийского университета в Беркли.

Ознакомившись с результатами Кука, Карп понял, как можно свести проблему выполнимости к задаче о клике. Он разработал несложный метод преобразования логического выражения в схему, похожую на схему дружеских связей, при котором выражение оказывалось выполнимым в том и только в том случае, когда в схеме существовала клика определенного размера. Отсюда следовало, что любой алгоритм решения задачи о клике заодно решает и проблему выполнимости. Кук доказал, что проблема выполнимости является самой трудной в NP; в работе Карпа было показано, что задача о клике не проще и потому тоже является самой трудной. Появление эффективного алгоритма для задачи о клике будет означать, что любую задачу из NP можно решить быстро, и докажет равенство классов P и NP.

Кук свел задачу о клике к проблеме выполнимости, Карп совершил обратный процесс, и в результате оказалось, что с вычислительной точки зрения эти две совершенно непохожие задачи эквивалентны. Проблему выполнимости можно решить быстро тогда и только тогда, когда быстро решается задача о клике, или – что то же самое – когда P равно NP.

Не ограничившись одной лишь задачей о клике, Карп рассмотрел еще девятнадцать важнейших задач и показал, что все они также являются самыми трудными. Среди них – задача о разбиении множества, задача коммивояжера, поиск гамильтонова пути, раскраска карт и поиск максимального разреза. Появление эффективного алгоритма хотя бы для одной даст нам возможность быстро решать их все и докажет равенство P и NP. Если же классы P и NP все-таки не совпадают, то ни одну задачу из списка – а их там двадцать одна, включая выполнимость, – нельзя решить быстро.

Ошибочно было бы полагать, что рассмотренные Карпом задачи надуманы и интересуют только математиков: большинство из них очень даже практические.

Возьмем, к примеру, компанию Coca-Cola. Под этой маркой производится более трех тысяч напитков по всему миру. Установка для розлива напитков способна выдавать сотни различных продуктов. В ее состав входит несколько разливочных машин, каждая из которых выполняет определенную последовательность операций, чтобы смешать ингредиенты. Одна машина может приготовить множество различных напитков. Задача установки – скоординировать работу всех разливочных машин и добиться наивысшей производительности, выдавая максимальное число напитков за минимальное время, т. е. решить проблему распределения подзадач, которая тоже входит в список Карпа и является самой трудной в NP.

Даже небольшое увеличение скорости производства за счет удачного распределения задач принесет компании-производителю миллионы долларов. С момента появления первых цифровых компьютеров ученые и программисты трудятся над созданием наилучших алгоритмов для решения этой проблемы, однако никому еще не удалось придумать такой алгоритм, который всегда выдавал бы на выходе оптимальное распределение. И это неудивительно: ведь Карп показал, что даже частные случаи проблемы распределения задач являются самыми трудными в NP.

На самом деле сложности возникают не только у производителей. Допустим, вы решили съездить в «Мир Уолта Диснея» в Орландо во время весенних каникул. Там, естественно, ажиотаж, а вам хочется посетить все самые лучшие аттракционы и при этом не слишком долго стоять в очередях. В неофициальном путеводителе по Диснейленду предлагаются варианты прогулок, призванные помочь вам сократить ожидание; впрочем, авторы путеводителя прекрасно сознают, что поставили перед собой практически неразрешимую задачу.

Задачу коммивояжера – так же как и проблему оптимального распределения, задачу о клике, задачу о максимальном разрезе и все остальные задачи из списка Карпа – пытались решить очень многие. Фактически все они бились над одним и тем же: ведь из работы Карпа следовало, что если эффективный алгоритм появится хотя бы для одной задачи, то с его помощью можно будет решить и все остальные.

Над решением этих разнообразных задач ученые трудились независимо. Все они потерпели поражение, из-за чего многие склоняются к тому, что P и NP не равны, хотя доказать это никто не может. Ясно лишь, что если эффективный алгоритм все-таки есть, то найти его будет очень и очень непросто. А пока операторы разливочных машин могут с чистой совестью заявить директору, что оптимального способа распределения просто не существует. Да и энтузиастам из Орландо тоже вряд ли удастся просчитать оптимальный маршрут по Диснейленду.

Все практически неразрешимые вычислительные задачи из списка Карпа уже были известны ранее, но Карп одним махом связал их воедино, и с этого момента проблема «P против NP» вышла на первый план.

Каждый год Ассоциация вычислительной техники вручает премию Тьюринга – «компьютерный» аналог Нобелевской премии, названый в честь Алана Тьюринга, который заложил основы теоретической информатики еще в 30-х годах XX века. В 1982 году за формулировку проблемы равенства P и NP премию получил Стивен Кук. Однако P и NP явно требовали большего, и в 1985 году Ричарда Карпа наградили за вклад в теорию алгоритмов, и в особенности – за список NP-полных задач.

Что в имени?

Названия «P» и «NP», которыми мы пользуемся и по сей день, впервые появились в работе Карпа. Однако для самых трудных задач из класса NP термина у него не было. Кук использовал крайне специфичное обозначение, deg({DNF tautologies}), которое расшифровывалось как «с полиномиальным уровнем сложности по отношению к сложности множества тавтологий, записанных в дизъюнктивной нормальной форме». Карп употреблял выражение «полиномиально полные». Оба варианта звучали как-то не очень.

В итоге с этим вопросом разобрался Дональд Кнут, который в 1974 году получил премию Тьюринга за исследования в области информатики и трехтомный (на тот момент) труд «Искусство программирования». В 1973 году, работая над четвертым томом монографии, Кнут в полной мере осознал важность проблемы равенства P и NP и решил взять инициативу на себя. Ученый запустил опрос населения по почте – не электронной, без которой он и сейчас прекрасно обходится. Впрочем, в те времена без электронной почты удавалось прекрасно обходиться всем.

В опросе предлагалось на выбор три названия: «титанические», «сверхтрудные» и «тяжелые», однако ни одно из них не смогло набрать достаточного количества голосов. В ответ люди присылали собственные варианты – от самых наивных вроде «неподдающиеся» или «упрямые» до откровенно насмешливых «не лыком шиты» или «черт ногу сломит».

Победителем конкурса стало название «NP-полные», которое после довольно бурных обсуждений предложили сотрудники Лабораторий Белла в Нью-Джерси. Этот термин, также отсутствовавший в первоначальном списке, обязан своим появлением математической логике, где система фактов, или аксиом, называется полной, если с ее помощью можно обосновать любое истинное высказывание в данной логической теории. Аналогичным образом, задача из класса NP называется NP-полной, если с ее помощью можно решить все остальные NP-задачи.

Кнут принял решение оставить этот вариант, хотя и чувствовал некоторую неудовлетворенность: ему хотелось, чтобы название состояло из одного слова и при этом давало интуитивное представление о трудных переборных задачах, т. е. было доступно самой широкой публике.

В 1974 году, излагая результаты последних исследований, Кнут написал: «Вообще-то термин „NP-полные“ кажется мне слишком техническим для широкой аудитории. Зато он по крайней мере адекватный».

Название «NP-полные» очень быстро вошло в стандартную терминологию. А Кнуту потребовалось почти сорок лет, чтобы закончить работу над четвертым томом.

Может, стоило все-таки попытаться придумать менее специфичное название? Причем не только для NP-полных задач, но и для самих классов P и NP? Ведь проблема равенства P и NP выходит далеко за пределы теоретической информатики, а использование этих загадочных аббревиатур, маскирующих не менее загадочные определения, затрудняет понимание проблемы непосвященными. Как бы то ни было, сейчас уже поздно: за прошедшие десятилетия термин прочно устоялся и заменить его было бы очень непросто даже при наличии достойной альтернативы.

Кнут, конечно, понимал, что если равенство классов докажут, то все его усилия по изобретению названия пропадут даром, поскольку NP-полные задачи «переедут» в класс P. Однако такая перспектива ученого не пугала. «Мне даже хочется, чтобы эта «неприятность» случилась, – пишет он. – Более того, за решение проблемы я объявляю награду: тот, кто первый докажет, что P = NP, получит от меня настоящую живую индейку». Что ж… докажите равенство P и NP – и получите миллион долларов и индейку в придачу!

После Карпа

Гигантские судоку

Судоку – это японская головоломка с числами. В классическом варианте используется квадратная сетка 9 × 9 (рис. 4.2).

Рис. 4.2. Классический вариант судоку

Рис. 4.3. Решение судоку из рис. 4.2

Цель игры – заполнить пустые клетки цифрами от 1 до 9 так, чтобы в каждой строке, каждом столбце и каждом жирно очерченном квадрате 3 × 3 эти цифры не повторялись.

Судоку лежит в классе NP, поскольку проверить имеющееся решение труда не составляет. Вы спросите, насколько сложно это решение найти? На самом деле все не так уж страшно: обычный среднестатистический компьютер при помощи простого перебора с возвратом решает классический вариант всего за несколько секунд.

А как обстоит дело с игрой на большом поле? Например, с сеткой 25 × 25, в которой каждая строка, каждый столбец и каждый мини-квадрат должны содержать все буквы от A до Y?

В этом случае вычисление займет уже гораздо больше времени, а с сеткой 100 × 100 вообще ни один современный компьютер не справится.

Рис. 4.4. Гигантское судоку

Поиск решения гигантского судоку – задача NP-полная. Считаете себя мастером судоку? Или знаете надежный способ решения какой-нибудь другой гигантской головоломки? Тогда в ваших руках ключ от решения задачи о выполнимости, задачи коммивояжера и тысячи других NP-полных проблем!

Есть еще много игр для одного игрока, решение которых представляет собой NP-полную задачу. Возьмем, к примеру, встроенного в Microsoft Windows «Сапера».

Рис. 4.5. «Сапер»

Число в ячейке говорит о количестве мин, расположенных в соседних с ней квадратиках – по вертикали, горизонтали и диагонали. Вы должны либо открыть ячейку, чтобы узнать это число, либо поставить на ней флажок, если думаете, что в ячейке бомба. Откроете бомбу – проиграете. Нахождение выигрышной стратегии в гигантском «Сапере» также представляет собой NP-полную задачу. На рисунке ниже показано расположение оставшихся бомб.

Другой пример – «Тетрис», в котором нужно передвигать и поворачивать фигурки так, чтобы образовывались сплошные горизонтальные ряды. Заполненный ряд тут же исчезает. Игра заканчивается, когда на экране больше не осталось свободных рядов; цель играющего – продержаться как можно дольше.

Фигурки бывают разных форм. В классическом варианте «Тетриса» вы не знаете, какая фигурка выпадет следующей. Впрочем, если бы вам даже заранее сообщили последовательность появления фигурок, выбор оптимальной стратегии все равно остался бы NP-полной задачей.

Рис. 4.6. Оставшиеся бомбы

Рис. 4.7. «Тетрис»

Кто бы мог подумать, что, научившись мастерски играть в судоку, «Тетрис» или «Сапер», можно доказать равенство P и NP и решить одну из задач тысячелетия!

Рис. 4.8. Виды фигурок в «Тетрисе»

Как насчет кубика Рубика? Наверняка это тоже NP-полная задача: ведь если даже освоение классического варианта 3 × 3 × 3 занимает столько времени, что уж говорить о больших кубах?

Рис. 4.9. Кубик Рубика. Фото: Том ван дер Занден

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

Верится с трудом, но это правда – кубик Рубика намного проще «Тетриса», «Сапера» и судоку.

А как обстоит дело с играми для двоих? Шахматы, шашки, го, «Отелло»? Если говорить о гигантских версиях, то они не уступают по сложности ни проблеме выполнимости, ни другим NP-полным задачам, однако к классу NP, тем не менее, не принадлежат. Вы спросите, почему? Потому что если я скажу, что белые обеспечат себе выигрыш, передвинув пешку на «e3», то вы вряд ли сможете быстро это проверить. Ученые полагают, что на самом деле эти игры намного труднее любой NP-полной задачи.

Мастера конспирации

Изоморфизм графов

В Королевстве насчитывается несколько сотен фанатов «Блейд Квеста» – массовой многопользовательской ролевой онлайн-игры. Как и в других играх подобного плана, участники здесь получают новую личность, или аватар; каждый исполняет роль определенного персонажа и общается с другими персонажами, за которыми тоже стоят реальные жители Королевства. В виртуальном мире дружеские связи сохраняются: те, кто дружат в жизни, становятся друзьями и в игре, а те, кто враждуют, заново проникаются взаимной неприязнью.

Джон, Изабель, Кевин, Лаура, Молли и Нэнси очень любят играть в «Блейд Квест».

Рис. 4.10. Любители «Блейд Квеста»

Их персонажей зовут Акрис, Лэмбо, Криард, Де Гарольд, Хрхрхр и Вирус, но кто под каким именем скрывается – неизвестно: эта информация пользователям игры недоступна, и они могут видеть только схему дружеских связей между персонажами.

Рис. 4.11. Аватары в «Блейд Квесте»

Проанализировав обе схемы, Лаура отправила остальным игрокам сообщение от имени своего аватара: «Я знаю, кто ты!» А вы уже догадались, кто есть кто?

Схемы будут соответствовать друг другу лишь в том случае, если Изабель – это Хрхрхр, Джон – Де Гарольд, Кевин – Криард, Лаура – Лэмбо, Молли – Акрис, а Нэнси – Вирус. Например, «реальная» Молли дружит с Лаурой и Нэнси, а ее аватар Акрис – с Лэмбо и Вирусом.

Установить, соответствуют ли друг другу подобные схемы, – это все равно что определить, изоморфны два графа или нет. Некоторые схемы сопоставить нельзя, другие – можно, иногда даже несколькими способами. Проблема изоморфизма графов лежит в NP, поскольку, зная, кто есть кто, можно легко проверить соответствие дружеских связей.

Вопрос о том, относится ли проблема изоморфизма также и к классу P, до сих пор открыт; никто пока не придумал хороший алгоритм, который всегда находил бы искомое соответствие в случае, если оно действительно есть. Мы также не знаем, является ли эта проблема NP-полной, хотя, по мнению ученых, некоторые признаки косвенно указывают на то, что не является. Изоморфизм графов стоит в ряду немногочисленных задач, занимающих некое промежуточное положение: они вроде бы труднее, чем задачи из P, но легче, чем задачи NP-полные, вроде поиска гамильтонова пути или максимального разреза.

Линейное программирование

Фэнси Франкс продает четыре вида колбасных изделий: франкфуртские сосиски, итальянские сосиски, братвурст и чоризо. У всех продуктов разный состав и время приготовления; все они продаются по разной цене, и стоимость ингредиентов также отличается. Сколько сосисок и колбасок каждого вида должна изготавливать Фэнси, чтобы получать максимальный доход?

Составить оптимальный план выпуска продукции – значит решить задачу максимизации прибыли при ограниченных ресурсах. Пусть фарш для одной франкфуртской сосиски стоит 1 доллар, для итальянской сосиски – 2 доллара, для братвурста – 3 доллара, а для чоризо – 4 доллара, и пусть дневной бюджет по расходам на мясо составляет 10000 долларов. Тогда количество франкфуртских, умноженное на один, плюс количество итальянских, умноженное на два, плюс количество братвурстов, умноженное на три, плюс количество чоризо, умноженное на четыре, не должно превышать 10000.

Поиск оптимального решения при наличии подобных ограничений представляет собой задачу линейного программирования. Множество потенциальных решений образует выпуклый многогранник в многомерном пространстве.

В 1947 году Джордж Данциг разработал симплекс-метод, который позволял решать задачи линейного программирования довольно-таки быстро. Суть метода заключается в последовательном обходе ребер многогранника в поисках оптимальных значений.

Но если все так просто, то зачем мы тут вообще говорим о линейном программировании? На самом деле в некоторых случаях симплекс-метод не умеет выдавать быстрый результат.

В 1979 году Леонид Хачиян придумал метод эллипсоидов, в котором исходный многогранник поэтапно сжимается до тех пор, пока от него не останется одно лишь оптимальное решение. Доказав эффективность этого метода, Хачиян тем самым «переместил» задачу линейного программирования в класс P, хотя на практике метод эллипсоидов работает гораздо дольше симплекс-метода. Работа Хачияна имела огромное теоретическое значение; в последующие десятилетия на основе метода эллипсоидов было создано множество нетривиальных алгоритмов.

Рис. 4.12. Выпуклый многогранник

Алгоритмов стало два, причем друг на друга они абсолютно не походили; один прекрасно работал на практике, другой – в теории.

В 1984 году индийский математик Нарендра Кармаркар разработал метод внутренней точки, который тоже, как и симплекс-метод, выполняет обход многогранника, вот только «ходит» он не по внешним точкам, а по внутренним. В теории метод внутренней точки сравним по быстроте с методом эллипсоидов, а на практике он после некоторых доработок может поспорить с симплекс-методом.

Так у задачи линейного программирования появилось целых три совершенно разных по сути алгоритма. Первый – симплекс-метод – хорошо работает на практике; второй – метод эллипсоидов – в теории; третий – метод внутренней точки – хорош и там и там. Не так уж плохо для задачи, которую до самого конца семидесятых считали практически неразрешимой!