Dlaczego programowanie liniowe w P, a programowanie liczb całkowitych jest trudne?

Programowanie liniowe (LP) jest w P, a programowanie liczb całkowitych (IP) jest trudne dla NP. Ponieważ jednak komputery mogą manipulować liczbami z ograniczoną precyzją, w praktyce komputer używa liczb całkowitych do programowania liniowego. Z tego powodu, czy LP i IP nie powinny należeć do tej samej klasy złożoności?

Nie mogę komentować, ponieważ wymaga 50 powtórzeń, ale pojawiają się pewne nieporozumienia, szczególnie komentarz Raphaela: „Ogólnie rzecz biorąc, ciągła domena oznacza, że ​​nie ma brutalnej siły (i nie ma sprytnej heurystyki, aby ją przyspieszyć)”.

To absolutnie nieprawda. Kluczową kwestią jest rzeczywiście wypukłość. Z wyjątkiem niektórych technicznych ograniczeń ograniczeń, minimalizowanie funkcji wypukłej (lub maksymalizowanie funkcji wklęsłej) w stosunku do zbioru wypukłego jest zasadniczo banalne, w sensie konwergencji wielomianowej w czasie.

Mówiąc luźniej, można powiedzieć, że istnieje zgodność między wypukłością problemu w optymalizacji „matematycznej” a wykonalnością zachłannych algorytmów w optymalizacji „informatyki”. Oznacza to, że oba umożliwiają lokalne metody wyszukiwania. Nigdy nie będziesz musiał cofać się w chciwym algorytmie i nigdy nie będziesz żałować kierunku opadania w wypukłym problemie optymalizacji. Lokalne ulepszenia funkcji celu ZAWSZE doprowadzą cię do globalnego optimum.

Tak nie jest w przypadku niewypukłego. W tym przypadku może istnieć globalne minimum, ale kilka lokalnych minimów, do których zawsze będzie wykorzystywany algorytm lokalnego zejścia, w taki sam sposób, jak robią to chciwe algorytmy, gdy stosuje się je do problemów NP. Czasami znajdują prawdziwy optymalny, przez większość czasu nie.

Krótka odpowiedź: ponieważ możesz użyć liczb całkowitych do symulacji booleanów dla SAT , ale jeśli nie ograniczysz się do tego, nie możesz w rzeczywistości symulować SAT. Otrzymasz wykonalną odpowiedź, ale nie ma ona już żadnego znaczenia w odniesieniu do jakiejkolwiek instancji SAT, którą próbujesz zasymulować.

$P \neq NP$

Programowanie liniowe jest „wydajne”, ponieważ przestrzeń rozwiązania może reprezentować pojedynczy wypukły wielościan. Jeśli ktoś próbuje znaleźć „najwyższy” wierzchołek na tym wielościanie (można zastosować transformację liniową do dowolnego problemu programowania liniowego, aby „wysokość” odpowiadała wielkości, która ma być zmaksymalizowana), to z dowolnego wierzchołka można podróżować wzdłuż krawędzi do najwyższy punkt bez konieczności schodzenia z góry. To, co sprawia, że ​​programowanie liczb całkowitych jest trudne, polega na tym, że nie ma ciągłej przestrzeni rozwiązań, ale zamiast tego istnieje wiele rozłącznych przestrzeni rozwiązań i nie ma możliwości stopniowego działania w kierunku optymalnego rozwiązania.

Pozostałe odpowiedzi są poprawne, ale uważam je za nieco techniczne. Załóżmy, że wymierzyłeś (wyeliminowałeś) macierz i szukasz dowolnego rozwiązania, a matryca wygląda następująco:

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

$Q$