Почему линейное программирование на P, а целочисленное программирование NP-сложно?

Линейное программирование (LP) находится в P, а целочисленное программирование (IP) является NP-сложным. Но поскольку компьютеры могут манипулировать только числами с конечной точностью, на практике компьютер использует целые числа для линейного программирования. Из-за этого не должны ли LP и IP находиться в одном классе сложности?

Я не могу комментировать, так как для этого требуется 50 повторений, но есть некоторые распространенные заблуждения, особенно комментарий Рафаэля «В общем, непрерывный домен означает, что нет грубой силы (и нет хитрой эвристики, чтобы ускорить ее)».

Это абсолютно неверно. Ключевым моментом действительно является выпуклость. За исключением некоторых технических ограничений, минимизация выпуклой функции (или максимизация вогнутой функции) над выпуклым множеством, по существу, тривиальна в смысле сходимости за полиномиальное время.

Грубо говоря, можно сказать, что существует соответствие между выпуклостью задачи в «математической» оптимизации и жизнеспособностью жадных алгоритмов в оптимизации «компьютерных наук». Это в том смысле, что они оба включают локальные методы поиска. Вам никогда не придется отступать в жадном алгоритме, и вам никогда не придется сожалеть о направлении снижения в выпуклой задаче оптимизации. Локальные улучшения целевой функции ВСЕГДА приведут вас ближе к глобальному оптимуму.

Это не так в невыпуклом случае. Здесь может существовать глобальный минимум, но несколько локальных минимумов, к которым всегда будет привлечен алгоритм локального спуска, точно так же, как это делают жадные алгоритмы применительно к NP-задачам. Иногда они находят истинный оптимум, чаще всего нет.

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

Трудный ответ на это заключается в том, что мы не знаем, что они не в одном классе сложности. Ни у кого нет доказательств того, что . Если бы мы поняли более глубокие причины, почему проблемы были такими разными, это потребовало бы, чтобы мы поняли, почему классы сложности были разными, чего у нас нет.$P \neq NP$

Линейное программирование является «эффективным», потому что пространство решений может быть представлено одним выпуклым многогранником. Если кто-то пытается найти «самую высокую» вершину на этом многограннике (можно применить линейное преобразование к любой задаче линейного программирования, чтобы «высота» соответствовала величине, которая должна быть максимизирована), то из любой вершины можно перемещаться вдоль ребер к самая высокая точка без необходимости идти "вниз". Что делает целочисленное программирование «трудным», так это то, что не существует непрерывного пространства решений, но вместо этого есть много непересекающихся областей решений, и нет никакого способа постепенно работать над оптимальным решением.

Другие ответы верны, но я нахожу их немного техническими. Предположим, что вы просмотрели (исключили) матрицу и ищете какое-либо решение, и матрица выглядит следующим образом:

column x1 x2 x3 x4 x5 x6 | solution
-----------------------------------
       1           1  1  | 3
          1              | 1
             1     1     | 2
                2  1  1  | 1  

В линейном программировании вы можете теперь установить неполюсные столбцы (x5, x6) на 0, а x4 на 0,5 и найти тривиальное решение. В целочисленном программировании вы не можете просто установить столбцы без опоры в 0. Решение труднее (NP-труднее) найти. Отметим также, что решения находятся в , так что это не имеет прямого отношения к конечной / бесконечной точности.$Q$