Czy wszystkie problemy z całkowitym programowaniem liniowym są trudne?

Jak rozumiem, problem przypisania występuje w P, ponieważ węgierski algorytm może go rozwiązać w czasie wielomianowym - O (n ³ ). Rozumiem również, że problem z przypisaniem jest całkowitym problemem programowania liniowego , ale strona Wikipedii stwierdza, że ​​jest to NP-Hard. Dla mnie oznacza to, że problem przypisania jest w NP-Hard.

Ale z pewnością problem przypisania nie może dotyczyć zarówno P, jak i NP-Hard, w przeciwnym razie P równałoby się NP? Czy strona Wikipedii oznacza po prostu, że ogólny algorytm rozwiązywania wszystkich problemów ILP to NP-Hard? Kilka innych źródeł twierdzi, że ILP jest trudna do NP, więc to naprawdę dezorientuje moje ogólne rozumienie klas złożoności.

Jeśli problemem jest NP-Hard, oznacza to, że istnieje klasa instancji tego problemu, których są NP-Hard. Jest całkiem możliwe, że inne konkretne klasy instancji mogą być rozwiązane w czasie wielomianowym.

Rozważmy na przykład problem znalezienia trójkolorowego wykresu . Jest to dobrze znany problem NP-Hard. Teraz wyobraź sobie, że jego instancje są ograniczone do wykresów, które są na przykład drzewami. Oczywiście w czasie wielomianowym można łatwo znaleźć 3-kolorowe zabarwienie drzewa (w rzeczywistości można również znaleźć 2-kolorowe zabarwienie).

Zastanów się przez chwilę nad problemami decyzyjnymi. Metoda udowodnienia twardości problemu decyzyjnego$P$opracowuje redukcję wielomianu (Karp) z innego problemu$Q$który jest znany jako NP-Hard. W tej redukcji pokazujesz, że istnieje funkcja$f$ który mapuje każdą instancję $q$ problemu $Q$ na przykład problemu $P$ takie, że: $q$ jest tak dla instancji $Q \iff f(q)$ jest tak dla instancji $P$. Oznacza to, że rozwiązanie$f(q)$ musi być „co najmniej tak trudne” jak rozwiązywanie $q$ samo.

Zauważ, że nie jest to wymagane do obrazu $f$ być równym zestawowi wystąpień $P$. Dlatego jest to całkowicie możliwe w przypadku problemu$P$ ograniczone do niektórych podzbiorów, aby nie było trudne.

Aby wrócić do pierwotnego pytania:

• Problem przypisania można rozwiązać w czasie wielomianowym, tzn. Rozwiązanie każdego wystąpienia problemu przypisania można obliczyć w czasie wielomianowym.
• ILP jest trudny do NP: ogólnie trudne może być obliczenie rozwiązania problemu ILP, tzn. Istnieją przypadki ILP, które są trudne.
• Niektóre konkretne przypadki ILP można rozwiązać w czasie wielomianowym.

Nie, specjalne przypadki mogą być łatwiejsze.

Rozważmy na przykład ten adres IP $a_i \geq 0$ dla $i \in [1..n]$:

$\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$

st i dla .$\quad\displaystyle\sum_{i=1}^n x_i \geq 1$
$\ \displaystyle x_i \in \mathbb{N}$$i \in [1..n]$

Znajduje minimum wśród (dla których nieuchronnie w optymalnym rozwiązaniu). Znalezienie minium liczby jest wyraźnie problemem wielomianowym.$a_1, \dots, a_n$$x_i=1$$n$

Możesz modelować wielomianowo rozwiązany problem jako adres IP. Nie oznacza to, że problem jest trudny do NP. Oznacza to po prostu, że nie jest znany algorytm wielomianowy do rozwiązania modelu IP twojego problemu (chyba że P = NP).

Tak jak zasugerowałeś, problem przypisania jest w P, ale twój model IP jest trudny do NP.

Nie, istnieje specjalny rodzaj programu liczb całkowitych, jeśli macierzą ograniczeń jest TUM (macierz całkowicie niemodularna), wówczas można ją rozluźnić w programie liniowym, który można rozwiązać w czasie wielomianowym.

Problem przypisania nie jest ILP, ale problemem LP, a zatem nie trudnym do NP.