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

17

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$

Istnieje parametr porządkowy , który jest obliczalną w czasie wielomianową funkcją o wartości rzeczywistej instancji. $r(x)$
Istnieje próg . Jest to albo rzeczywista stała, albo może zależeć od, to znaczy . $t$ $n=|x|$ $t=t(n)$
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$
Do niemal każdego o , mamy . $x$ $r(x)>t$ $x\notin L$
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?

cc.complexity-theory phase-transition

— Andras Farago
źródło

1

Prawdopodobnie zechcesz przeformułować warunek 5, ponieważ można go łatwo obejść, dodając niewielką część szumu do

aby upewnić się, że nie jest równy

dla dowolnego

. Ograniczenie

do funkcji

(z których oba można wykonać wlog), kontrprzykład musiałby być NP całkowitym problemem, którego żaden algorytm (ten obliczający

) nie może odgadnąć niezawodnie, tj. Jest trudny nawet z instancjami wybranymi z rozkładu jednolitego. Domyślam się, że przeznaczone do

, aby nie mieć dość tyle siłę wyrazu.

t

$t$

r (x)

$r(x)$

x

$x$

r

$r$

\pm 1

$\pm 1$

t = 0

$t = 0$

r

$r$

r

$r$

— Yonatan N

Tak więc, jeśli zdefiniujesz przejście fazowe, jak powyżej, wówczas są trudne przypadki, z dużym prawdopodobieństwem - w przypadku problemów NP całkowitych problemem jest zbadanie pewnej właściwości (dowodu) problemu, tak że najprawdopodobniej wystąpią trudne przypadki. Przeciwnie, jeśli istniał dowód, istnieją łatwe przypadki, z dużym prawdopodobieństwem. Na przykład losowy wykres może mieć gęstość krawędzi w pobliżu przejścia fazowego, co może mieć wpływ na łatwość rozwiązania problemu.

— user3483902

4

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:

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

— vzn
źródło

2

Dobry link do rozmowy Moshe Vardi, dzięki! Aby przybliżyć punkt, przejście fazowe zespołu NP-Complete nie oznacza trudności w złożoności instancji. M. Vardi nie wspomina o tym, ale propagacja badań rozwiązuje przypadki z milionami zmiennych / klauzul w pobliżu progu krytycznego (po stronie dodatniej) dla 3SAT i jest znana od pewnego czasu, że istnieją prawie pewne algorytmy wielomianowe dla cyklu HAM na Erdos -Renyi losowe wykresy.

— user834

0

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

— użytkownik3483902
źródło

2

Dokument połączony pokazuje dokładnie odwrotnie, że przejście fazowe cykli hamiltonowskich na losowych wykresach Erdosa-Renyi pokazuje przejście fazowe (prawdopodobnie pojawiające się cykle hamiltonowskie), ale nie wykazuje znaczącego wzrostu trudności obliczeniowych. Powszechnie wiadomo, że istnieją niemal pewne probabilistyczne algorytmy wielomianowe dla losowych grafów Erdosa-Renyi, wszędzie w fazie przejścia, nawet przy progu krytycznym. Przepraszam, ale muszę głosować za odpowiedzią.

— user834

-1

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.

— Daniel Pehoushek
źródło