У каждой проблемы NP есть поли-размерная формулировка ILP?

Поскольку целочисленное линейное программирование является NP-полным, существует сокращение Карпа от любой проблемы в NP до него. Я думал, что это подразумевает, что всегда есть формулировка ILP полиномиального размера для любой проблемы в NP.

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

complexity-theory np-complete reductions linear-programming Энди
источник

Вы должны указать пример или дать более полную цитату;)

hugomg

Существует полиномиальная редукция от каждой NP-полной задачи к любой другой NP-полной проблеме. Однако то, что мы знаем, что такое существует, не означает, что мы знаем, как его создать.

Джо

@ Хорошо, мы знаем, как уменьшить любую проблему в NP до 3-х сат, а также каждое практическое NP-полное доказательство проблемы происходит из цепочки сокращений с 3-сат, так что вы всегда можете составить сокращения от любой данной проблемы NPC до любой другой.

Энди

@ и разве ты не ответил на свой вопрос этим комментарием? Вы знаете, что каждый экземпляр проблемы NP может быть записан как полизированный экземпляр 3-SAT, и вы знаете, что экземпляр 3-SAT может быть записан как полизированный экземпляр ILP, а полином, примененный к полиному, является еще одним полиномом ... что еще вы делаете? ожидать от ответа?

Артем Казнатчеев

Когда кто-то говорит, что это первая поли-размерная формулировка, они имеют в виду, что это первая явно заданная такая формулировка. Сокращения, полученные с помощью SAT (даже если позаботиться обо всех деталях), выглядят не очень красиво и с ними трудно работать. Мы обычно хотим, чтобы составы были естественными и с ними легко работать.

Каве

Ответы:

Этот ответ в основном представляет собой резюме комментариев к вопросу выше.

Если проблема является NP-полной, ее действительно можно уменьшить до ILP, используя сокращения Карпа (Джо, Энди). Заявления о «формулировках полиномиального размера» от одной проблемы к другой, скорее всего, подразумеваются как более прямые формулировки, в отличие от многократных сокращений с помощью SAT (- Kaveh).

Реал Слав
источник

Да. Каждая проблема NP имеет формулировку ILP полиномиального размера.

Вот почему. Каждая проблема NP имеет формулировку полиномиального размера как пример SAT. Более того, все обычные логические операторы - логическое ИЛИ, логическое И, логическое НЕ и т. Д. - могут быть выражены в ILP с использованием постоянного числа переменных и неравенств на логический оператор. См. Экспресс логические логические операции в целочисленном линейном программировании (ILP) для получения подробной информации о том, как это сделать. Таким образом, при переходе от SAT к ILP мы получаем максимально возможное увеличение. Это подразумевает, что существует полиномиальная формулировка каждой проблемы NP как проблемы ILP.

DW
источник