Czy każdy problem NP ma wielocząsteczkowy preparat ILP?

14

Ponieważ całkowite programowanie liniowe jest zakończone NP, występuje zmniejszenie Karp z dowolnego problemu w NP. Pomyślałem, że to sugeruje, że zawsze istnieje wielomianowa formuła ILP dla dowolnego problemu w NP.

Ale widziałem artykuły na temat konkretnych problemów związanych z NP, w których ludzie piszą takie rzeczy, jak: „to jest pierwszy preparat wielowymiarowy” lub „nie ma znanego preparatu wielowymiarowego”. Dlatego jestem zaskoczony.

complexity-theory np-complete reductions linear-programming andy
źródło
8
Powinieneś wskazać przykład lub podać pełniejszy cytat;)
hugomg
1
Istnieje redukcja wielomianowa z każdego problemu NP-zupełnego do każdego innego problemu NP-zupełnego. Jednak fakt, że wiemy, że istnieje, nie oznacza, że ​​wiemy, jak go zbudować.
Joe
3
@Jo cóż, wiemy, jak zmniejszyć każdy problem w NP do 3-sat, a także każdy praktyczny dowód na problem NP-zupełny pochodzi z łańcucha redukcji z 3-sat, więc zawsze możesz skomponować redukcje z dowolnego problemu NPC do jakikolwiek inny.
andy
10
@andy, czy nie odpowiedziałeś tylko na swoje pytanie tym komentarzem? Wiesz, że każda instancja problemu NP może być zapisana jako spolaryzowana instancja 3-SAT i wiesz, że instancja 3-SAT może być zapisana jako spolaryzowana instancja ILP, a wielomian zastosowany do wielomianu jest kolejnym wielomianem ... co więcej oczekiwać od odpowiedzi?
Artem Kaznatcheev
2
Kiedy ktoś mówi, że jest to pierwszy preparat poli-size, co mają na myśli to, że jest to pierwszy wyraźnie podane takie sformułowanie. Redukcje uzyskane przez SAT (nawet jeśli dba się o wszystkie szczegóły) nie wyglądają ładnie i są trudne do pracy. Zwykle chcemy formuł, które są naturalne i łatwe w obróbce.
Kaveh

Odpowiedzi:

5

Ta odpowiedź jest głównie podsumowaniem komentarzy do powyższego pytania.

Jeśli problem jest NP-zupełny, można go rzeczywiście zredukować do ILP, stosując redukcje Karpa (- Joe, andy). Roszczenia „formulacji wielomianowych” z jednego problemu do drugiego są prawdopodobnie rozumiane jako bardziej bezpośrednie formulacje, w przeciwieństwie do wielokrotnych redukcji poprzez SAT (- Kaveh).

Realz Slaw
źródło
1

Tak. Każdy problem NP ma wielomianową formułę ILP.

Oto dlaczego. Każdy problem NP ma formułę wielomianową jako przykład SAT. Co więcej, wszystkie zwykłe operatory logiczne - logiczne OR, logiczne AND, logiczne NOT itp. - mogą być wyrażone w ILP, przy użyciu stałej liczby zmiennych i nierówności na operator logiczny. Zobacz Express logiczne operacje logiczne w programowaniu liniowym całkowitym zerowym (ILP), aby dowiedzieć się, jak to zrobić. W ten sposób uzyskujemy co najwyżej stałe powiększenie podczas przechodzenia z SAT do ILP. Oznacza to, że istnieje wielomianowe sformułowanie każdego problemu NP jako problemu ILP.

DW
źródło