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

35

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?

complexity-theory polynomial-time

— Sasha the Noob
źródło

7

Dodając trochę do odpowiedzi jmite: W wielu przypadkach ograniczenia integralności znacznie utrudniają problem. Na przykład problem plecakowy ułamkowy może być rozwiązany w czasie wielomianowym, chociaż problem plecaka całkowitego jest NP-trudny. Jest to więc nie tylko coś, co dotyczy LP i IP.

— user340082710,

7

Nawet jeśli weźmiemy pod uwagę, że komputery wykonują operacje na liczbach całkowitych, nie oznacza to, że zwrócone rozwiązanie jest liczbą całkowitą; może być racjonalny, tj. stosunek dwóch liczb całkowitych. A to daje dużo większą elastyczność. I oczywiście nie zawsze możemy przekonwertować racjonalne rozwiązanie na realne rozwiązanie dla własności intelektualnej. Ogólnie rzecz biorąc, IP będzie miało więcej ograniczeń dla zmiennych niż tylko prośba o integralne rozwiązanie. Pomyśl o programie liczb całkowitych .

0, 1

$0,1$

— megas

1

Jeśli nie chcesz, manipulowanie liczbami z nieskończoną precyzją jest szczególnie trudne, zwłaszcza gdy są one racjonalne. Skończona precyzja jest jedynie optymalizacją w celu skrócenia czasu działania.

2

@Hurkyl „Nie jest trudno manipulować liczbami z nieskończoną precyzją, jeśli chcesz, zwłaszcza gdy są one racjonalne”. Istnieje ścisły podzbiór liczb rzeczywistych zwany liczbami obliczalnymi, który obejmuje liczby wymierne + liczby takie jak sqrt (2) itp. I jest zdefiniowany jako zbiór liczb obliczalnych przez maszynę Turinga. Te, których tam nie ma, z definicji nie mogą być przetwarzane przez komputer.

— Sasha the Noob

1

@SashatheNoob To, co mówisz, nie jest tak naprawdę sprzeczne z tym, co powiedział Hurkyl. Liczby obliczalne nie mają z góry określonego maksymalnego limitu ich dokładności (jest to dowolnie ustawione na dowolną wartość, pod warunkiem, że maszyna Turinga ma wystarczającą ilość pamięci - stąd nieskończona precyzja). Aby powiedzieć, że podzbiór liczb obliczalnych obejmuje wszystkie liczby wymierne, przyznajesz, że komputery mogą manipulować liczbami z nieskończoną precyzją. (Oświadczenie Hurkyl jest absolutnie prawdziwe. Fakt, że precyzja jest ograniczona dla niektórych typów danych, jest jedynie optymalizacją.)

— BrainSlugs83

9

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.

— Benjamin Lindqvist
źródło

23

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$

— jmite
źródło

21

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.

— supercat
źródło

2

— Słowo

1

Czy to wzgórze nie wspina się metodą simpleksową, o której żaden wariant nie jest znany w najgorszym przypadku?

— jbapple

1

Istnieje wiele problemów, które łatwiej rozwiązać w dyskretnych przestrzeniach (co umożliwia dyskretne wyszukiwanie) niż w przestrzeni ciągłej.

— Raphael

@Raphael: czy możesz podać przykłady takich problemów? Myślałem o tym i nie mogę wymyślić wielu.

— cody

@cody Znalezienie na przykład maksimów / minimów (jednowymiarowych) funkcji. Zobacz tutaj ładny przykład, który staje się dostępny dopiero po zauważeniu, że możemy ograniczyć skończoną przestrzeń wyszukiwania do skończonej. Zauważ, że płyty LP są w ten sposób wyjątkowe: zauważając, że musimy brać pod uwagę tylko narożniki wielościanu, otrzymujemy skończoną przestrzeń poszukiwań. Ogólnie rzecz biorąc, ciągła domena oznacza, że nie ma brutalnej siły (i nie ma sprytnej heurystyki, aby ją przyspieszyć).

— Raphael

3

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$

— Albert Hendriks
źródło