Ranking trudności trudnych problemów NP w praktyce

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!

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ą.