Jak często występuje przejście fazowe w problemach z NP-zupełnym?

Powszechnie wiadomo, że wiele problemów z kompletnym NP wykazuje przejście fazowe. Interesuje mnie przejście fazowe w odniesieniu do ograniczenia w języku, a nie twardości danych wejściowych w stosunku do algorytmu.

Aby pojęcie było jednoznaczne, formalnie zdefiniujmy go w następujący sposób. Język wykazuje przejście fazowe (w odniesieniu do powstrzymywania), jeśli$L$

1. Istnieje parametr porządkowy , który jest obliczalną w czasie wielomianową funkcją o wartości rzeczywistej instancji.$r(x)$

2. Istnieje próg . Jest to albo rzeczywista stała, albo może zależeć od, to znaczy .n = | x $t$$n=|x|$$t=t(n)$

3. Do niemal każdego o mamy . ( Prawie każdy oznacza tutaj: wszyscy oprócz znikomej liczby, czyli proporcja zbliża się do 1, jak ).$x$$r(x)<t$$x\in L$$n\rightarrow\infty$

4. Do niemal każdego o , mamy .$x$$r(x)>t$$x\notin L$

5. Dla prawie każdego utrzymuje, że . (To znaczy region przejściowy jest „wąski”).$x$$r(x)\neq t$

Wiele naturalnych problemów NP-zupełnych wykazuje przejście fazowe w tym sensie. Przykładami są liczne warianty SAT, wszystkie właściwości wykresu monotonicznego, różne problemy związane z satysfakcją z ograniczeń i prawdopodobnie wiele innych.

Pytanie: Jakie są „miłe” wyjątki? Czy istnieje naturalny problem NP-zupełny, który (prawdopodobnie) nie ma przejścia fazowego w powyższym sensie?

eksperci w tej dziedzinie zasadniczo twierdzą, że przejścia fazowe są uniwersalną cechą kompletnych problemów NP, chociaż nie zostało to jeszcze dokładnie sformułowane / udowodnione i nie jest jeszcze szeroko rozważane / rozpowszechniane w większej dziedzinie (bardziej wynika z orientacji empirycznej gałąź studiów). to prawie otwarta hipoteza. istnieją mocne dowody. nie ma żadnych prawdopodobnych kandydatów na kompletne problemy związane z NP w fazie przejściowej. oto dwie referencje, które obsługują ten pov:

• Przejścia fazowe w problemach NP-zupełnych: wyzwanie dla prawdopodobieństwa, kombinatoryki i informatyki / Moore

• Zachowanie przejścia fazowego / Walsh (ppt)

oto przybliżony szkic prawdy tego twierdzenia. ma to związek z P zawartym w NP complete. kompletny problem / język NP musi mieć instancje, które można rozwiązać w czasie P, i inne, które są możliwe do rozwiązania w czasie wykładniczym (lub co najmniej super-wielomianowym), jeśli P ≠ NP. ale zawsze musi istnieć sposób na „zgrupowanie” instancji P z instancji „innych niż P”. dlatego zawsze muszą istnieć pewne „kryteria przejścia” między instancjami P i innymi niż P. w skrócie, być może zjawisko to jest ściśle powiązane z P ≠ NP!

kolejny szorstki argument: wszystkie problemy NP całkowite są wymienne poprzez redukcje. jeśli przejście fazowe występuje w jednym, należy je znaleźć we wszystkich.

bardziej poszlakowe dowody na to, ostatnio (~ 2010) wykazano, że przejście fazowe pojawia się dla niższych granic w obwodach monotonicznych w celu wykrywania kliki na losowych grafach.

• Średnia złożoność przypadków wykrywania klików / Rossman

pełne ujawnienie: Moshe Vardi badał przejścia fazowe szczególnie w SAT i ma bardziej sceptyczny kontrast w tym wykładzie / wideo.

• Przejścia fazowe i złożoność obliczeniowa

Wykresy zastosowaniu takiego jak wykresy, które przedstawiają wykresy wybranych losowo równomiernie ze zbioru wszystkich wykresach które $G_{n,m}$$n$$m$ m. Przejście fazowe dla losowego wykresu$\binom{n}{2}$$m$$G_{n,m}$

Kolorystyka C regularnych wykresów D ma szereg dyskretnych przejść, niezbyt fazowanych, chyba że się rozciągniesz.

Oto tabela wyników kolorowania, które prześlę na SAT17. Zauważ, że 3 zabarwienie 6 zwykłych wykresów jest niemożliwe z wyjątkiem kilku przykładów. Podobnie 4 zabarwienie wykresów dziesiątego stopnia ... Wykresy C3D5N180 są dość trudne. C4D9 Golden Point jest tylko niepewnie na C4D9N180; Wykresy C4D9 są najtrudniejszymi 4cnfs pod względem wielkości, jakie spotkałem, więc C4D9 kwalifikuje się jako „Hard Spot”. Przypuszcza się, że złoty punkt C5D16 istnieje, ale będzie w trudnym miejscu od 5 do 6 kolorów.

          Universal Constants of Regular Graph Coloring

Wzory barwiące mają zmienne lgC na wierzchołek, co łącznie daje zmienne lgC * N; krawędzie mają klauzule kolorujące C, co daje łącznie klauzule C * M. Istnieje kilka dodatkowych klauzul na wierzchołek, aby wykluczyć dodatkowe kolory. Złote punkty są najmniejszymi N, tak że: C możliwość pokolorowania na wykresach stopnia D z N wierzchołkami jest prawie zawsze zadowalająca, z prawdopodobieństwem bliskim 1. Dla wysokiego prawdopodobieństwa N przypadkowych wystąpień było zadowalających. Dla Very High N * N były zadowalające. W przypadku Super High losowe przypadki N * N * N były zadowalające.

Punkty złotego kolorowania o wysokim prawdopodobieństwie (1 - 1 / N) to:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Punkty złotego barwienia o bardzo wysokim prawdopodobieństwie (1 - 1 / (N * N)) to:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Punkty złotego zabarwienia o bardzo wysokim prawdopodobieństwie (1 - 1 / (N * N * N)) to:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Wszystkie przypadkowe przypadki w badaniu były zadowalające. Liniowe punkty prawdopodobieństwa sprawdziły setki zadowalających wzorów. Kwadratowe punkty prawdopodobieństwa sprawdziły dziesiątki tysięcy zadowalających wzorów. Sześcienne punkty prawdopodobieństwa sprawdzały setki tysięcy zadowalających wzorów. Punkty C4D9 i C5D13 są trudne. Przypuszcza się, że punkt C5D16 istnieje. Jedna przypadkowa instancja z pięciu kolorowych szesnastych stopni potwierdzi przypuszczenie.