Ranking trudności trudnych problemów NP w praktyce

15

To pytanie jest ściśle związane z innym postem: Przejścia fazowe w trudnych problemach NP, ale jest nieco inne. Chociaż pytanie dotyczy twardości poszczególnych przypadków trudnych problemów NP, chodzi o uszeregowanie trudności tych samych przypadków.

Istnieje wiele bibliografii na temat efektu znanego jako Przejście Fazowe . W szczególności w przypadku losowych wzorów 3-SAT w łączonej postaci normalnej (CNF) wiadomo, że istnieje wartość R stosunku klauzul do zmiennych, tak że dla wszystkich r <R wzór można spełnić z dużym prawdopodobieństwem a dla r> R wzór jest niezadowalający z dużym prawdopodobieństwem. Efekt przejścia fazowego występuje w pobliżu R i ma niezwykły efekt, że rozwiązanie problemu satysfakcji dla tych formuł jest niezwykle trudne w praktyce.

Ponieważ w celu udowodnienia twardości NP danego problemu należy wykazać, że występuje w nim wielomianowa redukcja Turinga problemu NP-zupełnego i że problemy, które są NP-całkowite, można przekształcić między nimi w czas wielomianowy, a następnie naturalnie powstaje następujące pytanie:

Czy w praktyce można ocenić trudność trudnych problemów z NP, wykorzystując jako wskaźnik wskaźnik przejścia fazowego 3-SAT CNF? Intuicja polega na tym, że jeden problem P1 może być trudniejszy niż P2, jeśli jego kodowanie 3-SAT jest bliższe R (o którym wiadomo, że jest bliskie 4.2). Zauważ, że ten pomysł niekoniecznie wiąże każdą konkretną instancję z konkretną trudnością, po prostu szereguje je.

Istnieje wiele kontrargumentów, w tym:

  1. Formuła przejścia fazowego 3-SAT CNF ma zastosowanie do formuł losowych. Jednak szczególny przypadek innego problemu ma pewną strukturę, która mogłaby zostać wykorzystana przez solwery dla tego problemu - zauważył to już Peter Shor we wspomnianym pytaniu.
  2. Może się zdarzyć, że konkretne kodowanie zastosowane do przekształcenia poszczególnych przypadków w naszym problemie na 3-SAT odgrywa kluczową rolę w stosunku klauzul do zmiennych prowadzących do wprowadzających w błąd wartości, stąd błędne klasyfikacje --- ta kwestia jest podnoszona przez Kaveha w komentarze do tego pytania.
  3. Serge (zgodnie z moim rozumieniem z jego komentarza do tego pytania) podnosi kwestię, że można sztucznie skomplikować pierwotny trudny problem NP, tak że powstaje wzór 3CNF, który zmienia stosunek klauzul do zmiennych, zachowując jednocześnie satysfakcję.

Jeśli chodzi o 1, wszystkie problemy mogą mieć tę samą klasę regularności, aby mogły mieć zastosowanie problemy z rankingiem (zamiast charakteryzowania trudności); jak w przypadku 2, istnieją kodowania w konkretnych problemach, o których wiadomo, że nie są zbędne, zgodnie z regułą propagacji jednostek, tak więc powinny być one preferowane i być może unikną tych błędnych klasyfikacji. Przykładem jest Sideris i in., 2010 w przypadku planowania propozycji. Jeśli chodzi o 3, Cheeseman i in., 1991 już rozważali kwestię, czy odwzorowania między problemami zachowują efekt przejścia fazowego, a ich wstępne eksperymenty wydają się potwierdzać ich przypuszczenia, pod warunkiem, że zmniejszy się pierwotny problem NP, a nawet że „ można dodatkowo zredukowane poprzez zastosowanie rezolucji do klauzul ”.

Czy to wszystko ma dla ciebie sens? czy znasz jakieś odniesienia bibliograficzne na ten temat? Wszelkie wskazówki zostaną w dużej mierze uznane!

Carlos Linares López
źródło
Sądzę, że odpowiedź będzie zależeć od konkretnej redukcji SAT, której się używa, chociaż może istnieć sposób na obejście tego.
Kaveh
5
Jeszcze jednym kontrargumentem jest to, że zawsze można dodać bardzo rzadki lub bardzo gęsty zadowalający rozłączny składnik do wzoru 3CNF, zmieniając stosunek klauzul do zmiennych i zachowując jego zadowalalność.
Serge Gaspers
@Kaveh: wielkie dzięki za komentarze! Pomysł polegałby na zastosowaniu nie redundantnego kodowania do 3-SAT, jak w [Sideris i in. 2010]. Nie twierdzę, że to zadziała, ale wydaje się to słuszne. Zredagowałem pytanie z twoim komentarzem. Dzięki jeszcze raz!
Carlos Linares López
1
@Serge: dobra uwaga, Serge! [Cheesemann i in., 1991] badali już pytanie, czy odwzorowania między problemami zachowują efekt przejścia fazowego zarówno dla problemów NP, jak i problemów w P (aby udowodnić, że nie stają się NP, gdy sztucznie rozszerzono je na 3-SAT, na przykład ), a ich wyniki potwierdzają te twierdzenia, pod warunkiem że zaczną one od pewnych wstępnych redukcji, być może stosując zasadę propagacji jednostkowej. Zredagowałem moje pytanie z twoimi komentarzami. Wielkie dzięki!
Carlos Linares López
@all: dziękuję bardzo za uwagę poświęconą mojemu pytaniu! To jest moje pierwsze pytanie tutaj (i na pewno opublikuję inne w przyszłości). Zrobiłem wrażenie, że w mniej niż 24 godziny otrzymało 125 wizyt, 7 głosów i jedna osoba oznaczyła to jako ulubione. Dziękuję wam wszystkim!
Carlos Linares López

Odpowiedzi:

13

Chociaż nie jest wykluczone, że wspomniane przeszkody techniczne można jakoś pokonać, myślę, że obecnie jest bardzo mało motywacji do tego, z tego prostego powodu, że (przynajmniej o ile mi wiadomo) trudność NP-trudna problemy w praktyce wydają się, empirycznie, nie mieć wiele wspólnego z bliskością przejścia fazowego 3-SAT.

Porównaj to z innymi sposobami uszeregowania problemów trudnych z NP pod względem trudności: istnieje pewna empiryczna korelacja między trudnymi w praktyce problemami z NP a trudnymi do oszacowania problemami z NP, które są łatwe do przybliżenia lub które można ustalić w oparciu o ustalone parametry (w sensie sparametryzowanej złożoności). W tych przypadkach opracowano odpowiednie pojęcia redukcji, które częściowo wyjaśniają obserwacje empiryczne. Jednak obecnie wydaje się, że nie ma empirycznych wskazówek, że większość problemów trudnych w NP, które są trudne w praktyce, są trudne ze względu na ich bliski związek z instancjami 3-SAT w pobliżu przejścia fazowego. Nie ma więc większego sensu opracowywanie teorii „wyjaśniającej” coś, co w praktyce nie wydaje się prawdą.

Timothy Chow
źródło
2
Pozytywne. Byłbym zainteresowany odniesieniem do empirycznego rankingu problemów trudnych dla NP.
Aaron Sterling
Pozytywnie oceniany! Ale jako Aaron byłbym bardzo zainteresowany również niektórymi referencjami na temat rankingu problemów trudnych dla NP. Daj mi parę, a chętnie oznaczę to pytanie jako odpowiedź! (szczerze mówiąc, z pewnością zrobię to za kilka dni, nawet jeśli nie dostarczysz żadnych referencji na śliniaczek) Jeszcze raz dziękuję Tymoteusz!
Carlos Linares López
1
W.
Tymotka!! Wielkie dzięki naprawdę !!! To bardzo miłe z twojej strony, że podajesz ten numer referencyjny !! Dziękuję bardzo!!
Carlos Linares López