Przykłady przejść fazowych twardości

Załóżmy, że mamy problem sparametryzowany parametrem p o wartości rzeczywistej, który jest „łatwy” do rozwiązania, gdy i „twardy”, gdy p = p 1 dla niektórych wartości p 0 , p 1 .$p=p_0$$p=p_1$$p_0$$p_1$

Jednym z przykładów jest liczenie konfiguracji spinów na wykresach. Licząc prawidłowe ważone kolory, niezależne zestawy, podgrupy Eulera odpowiadają funkcjom podziału modeli hardcore, Potts i Ising, które są łatwe do przybliżenia dla „wysokiej temperatury” i trudne dla „niskiej temperatury”. W przypadku prostego MCMC przejście fazy twardości odpowiada punktowi, w którym czas mieszania przeskakuje z wielomianu na wykładniczy ( Martineli, 2006 ).

Innym przykładem jest wnioskowanie w modelach probabilistycznych. „Upraszczamy” dany model, przyjmując jego kombinację , p z modelem „wszystkie zmienne są niezależne”. Dla p = 1 problem jest trywialny, dla p = 0 jest on trudny do rozwiązania, a próg twardości leży gdzieś pośrodku. W przypadku najpopularniejszej metody wnioskowania problem staje się trudny, gdy metoda nie jest zbieżna, a moment, w którym to się dzieje, odpowiada przejściu fazowemu (w sensie fizycznym) określonego rozkładu Gibbsa ( Tatikonda, 2002 ).$1-p$$p$$p=1$$p=0$

Jakie są inne interesujące przykłady „skoku” twardości, gdy zmienia się jakiś parametr ciągły?

Motywacja: aby zobaczyć przykłady innego „wymiaru” twardości oprócz typu wykresu lub logiki

W standardowym przybliżeniu najgorszego przypadku istnieje wiele ostrych progów, ponieważ współczynnik przybliżenia jest zmienny.

Na przykład, dla 3LIN, spełniającego tyle podanych boolowskich równań liniowych dla 3 zmiennych, istnieje prosty algorytm aproksymacji losowego przypisania dla aproksymacji 1/2, ale każde przybliżenie lepsze niż niektóre t = 1/2 + o (1) jest już tak trudny jak dokładny SAT (przypuszcza się, że wymaga czasu wykładniczego).

Nie jestem do końca pewien, czy tego rodzaju problemu szukałeś, ale przejście fazowe problemów NP-Complete jest (jak dotąd) dobrze znanym zjawiskiem. Zobacz artykuły Briana Hayesa „Can't Get No Satisfaction” na temat przejścia fazowego 3-SAT i „The Easy Easy Hard Problem” na temat przejścia fazowego z podziałem liczb, na niektóre popularne artykuły na ten temat.

Selman i Kirkpatrick jako pierwsi wykazali liczbowo, że przejście fazowe dla 3-SAT miało miejsce, gdy stosunek klauzul do zmiennych wynosił około 4,3.

Gent i Walsh jako pierwsi wykazali liczbowo, że przejście fazowe dla problemu podziału liczb wystąpiło, gdy stosunek bitów do długości listy wynosił około 1. Później zostało to potwierdzone analitycznie przez Borgsa, Chayesa i Pittela .

Traveling Salesman, Graph Coloring, Hamiltonian Cycle, między innymi, również wydają się mieć przejścia fazowe dla odpowiedniej parametryzacji tworzenia instancji problemu. Myślę, że można śmiało powiedzieć, że powszechnie uważa się, że wszystkie problemy z NP-Complete wykazują przejście fazowe dla odpowiedniej parametryzacji.

Związana z (niektórymi) modelami szumu do obliczeń kwantowych jest wartość progowa dla poziomu hałasu, powyżej której głośne bramki mogą być symulowane przez bramki Clifford, tak że procesy obliczeń kwantowych stają się efektywnie symulowane. Na początek zobacz Plenio i Virmani, Górne granice progów tolerancji na uszkodzenia w głośnych komputerach kwantowych opartych na Cli ff ff (arXiv: 0810.4340v1).

Rozwiązane modele takie jak ten informują nas o wszechobecnym problemie praktycznym: dla określonego fizycznego układu kwantowego w kontakcie ze zbiornikiem termicznym (być może w temperaturze zerowej), poziomy hałasu związane z tym zbiornikiem termicznym poniżej lub powyżej progu dla efektywnej symulacji z klasycznym zasoby? Jeśli to drugie, jakie algorytmy symulacji są optymalne?

$k$$k$$k$

$f(k)$$k$$f(k)$$2^k$$k$$1 \le f(k) < 2^k$

$k$$n$$k$$f(k)/2^k$

$f(k)$$f(k)+1$

• Jan Kratochvíl, Petr Savický i Zsolt Tuza, Jeszcze jedno wystąpienie zmiennych powoduje, że satysfakcja przeskakuje z Trivial do NP-Complete , SIAM J. Comput. 22 (1) 203–210, 1993. doi: 10.1137 / 0222015

$f(k)$$f(k) = \Theta(2^k/k)$

• Heidi Gebauer, Rozproszenie przypuszczenia sąsiedztwa z implikacjami dla SAT , Combinatorica 32 (5) 573–587, 2012. doi: 10.1007 / s00493-012-2679-y (preprint)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, Lokalny lemat jest trudny dla SAT , SODA 2011.