Co rozumiemy przez heurystyczne argumenty fizyki statystycznej?

Słyszałem, że w fizyce statystycznej istnieją heurystyczne argumenty, które dają wyniki w teorii prawdopodobieństwa, dla których rygorystyczne dowody są albo nieznane, albo bardzo trudne do uzyskania. Jaki jest prosty zabawkowy przykład takiego zjawiska?

Byłoby dobrze, gdyby odpowiedź obejmowała niewielkie podstawy fizyki statystycznej i mogła wyjaśnić, czym są te tajemnicze heurystyki i jak można je nieformalnie uzasadnić. Być może ktoś może wskazać szeroki obraz tego, jak wiele z tych heurystyk może być rygorystycznie uzasadnione i jak pasuje do tego program Lawlera, Schramma i Wernera.

Drugi akapit odpowiedzi RJK zasługuje na więcej szczegółów.

Niech będzie formułą w spójnej postaci normalnej, z m klauzulami, n zmiennymi i co najwyżej k zmiennymi na klauzulę. Załóżmy, że chcemy ustalić, czy ma zadowalające zadanie. Formula jest przykładem problemu decyzyjnego k-SAT.ϕ $\phi$$\phi$$\phi$

Kiedy klauzul jest niewiele (więc m jest dość małe w porównaniu do n), prawie zawsze można znaleźć rozwiązanie. Prosty algorytm znajdzie rozwiązanie w przybliżeniu liniowym czasie w rozmiarze formuły.

Kiedy jest wiele klauzul (więc m jest dość duży w porównaniu do n), prawie zawsze jest tak, że nie ma rozwiązania. Można to pokazać argumentem liczącym. Jednak podczas wyszukiwania prawie zawsze możliwe jest przycinanie dużych części przestrzeni wyszukiwania za pomocą technik spójności, ponieważ wiele klauzul oddziałuje tak intensywnie. Stwierdzenie niezadowolenia można wówczas zwykle zrobić skutecznie.

• V. Chvátal i B. Reed. Mick dostaje trochę (szanse są po jego stronie) , FOCS 1992. doi: 10.1109 / SFCS.1992.267789

W 1986 Fu i Anderson przypuszczali, że istnieje związek między problemami optymalizacyjnymi a fizyką statystyczną, oparty na systemach ze spinu. Chociaż używali zdań takich jak

Intuicyjnie system musi być wystarczająco duży, ale trudno jest sprecyzować.

faktycznie dają konkretne prognozy.

• Y Fu i PW Anderson. Zastosowanie mechaniki statystycznej do problemów NP-zupełnych w optymalizacji kombinatorycznej , J. Phys. A. 19 1605, 1986. doi: 10.1088 / 0305-4470 / 19/9/033

Na podstawie argumentów fizyki statystycznej Zecchina i współpracownicy wysunęli hipotezę, że k-SAT powinien stać się trudny, gdy jest bliski wartości krytycznej. Dokładna wartość krytyczna zależy od k, ale mieści się w zakresie od 3,5 do 4,5 dla 3-SAT.$\alpha = m/n$

• Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Określanie złożoności obliczeniowej na podstawie charakterystycznych „przejść fazowych” , Nature 400 133–137, 1999. ( doi: 10.1038 / 22055 , wersja bezpłatna )

Friedgut przedstawił rygorystyczny dowód na te heurystyczne argumenty. Dla każdej stałej wartości k istnieją dwa progi . Dla poniżej istnieje zadowalające przypisanie z dużym prawdopodobieństwem. Dla wartości powyżej formuła jest niezadowalająca z dużym prawdopodobieństwem. α α 1 α α 2$\alpha_1 < \alpha_2$$\alpha$$\alpha_1$$\alpha$$\alpha_2$$\phi$

• Ehud Friedgut (z dodatkiem Jeana Bourgaina), ostre progi właściwości grafu i problem sata$k$ , J. Amer. Matematyka Soc. 12 1017–1054, 1999. ( PDF )

Dimitris Achlioptas pracował nad wieloma pozostałymi zagadnieniami i wykazał, że powyższy argument dotyczy również problemów związanych z satysfakcją z ograniczeń. Dozwolone jest użycie więcej niż dwóch wartości dla każdej zmiennej. Jeden kluczowy artykuł pokazuje rygorystycznie, dlaczego algorytm propagacji ankiety działa tak dobrze do rozwiązywania losowych instancji k-SAT.

• A. Braunstein, M. Mézard, R. Zecchina, Propagacja badania: algorytm satysfakcji , Struktury losowe i algorytmy 27 201–226, 2005. doi: 10.1002 / rsa.20057
• D. Achlioptas i F. Ricci-Tersenghi, O geometrii rozwiązanie-przestrzeń losowych problemów z ograniczeniami losowymi, STOC 2006, 130–139. ( preprint )

Istnieje bardzo niedawna ankieta przeprowadzona przez Lawlera na temat SLE . Musisz znać trochę złożonej analizy.

Chociaż nie jest to bezpośrednio związane z twoim pytaniem, być może mógłbyś zapoznać się z kilkoma artykułami Achlioptas, które również mieszczą się pod parasolem „formalizacji heurystyk fizyków”, choć z punktu widzenia teoretycznego informatyka. A może głębiej w perspektywie statphys możesz przejrzeć niektóre prace Zecchiny .

Myślę, że warto dodać, że tak zwane „wyniki” fizyków - z których większość należy nazwać przypuszczeniami - w tej bardzo szerokiej kategorii problemów polegają prawie w takim samym stopniu (lub nawet więcej) na eksperymentach numerycznych, jak ( niż) na heurystycznych argumentach.

(rozwinięcie mojego komentarza)

„Fizyczną intuicją” kryjącą się za metodami statystycznymi stosowanymi w obliczeniach jest Maximum Entropia (a-la Jaynes) oraz powiązane metody stochastyczne, takie jak Symulowane Wyżarzanie lub Wyżarzanie Deterministyczne . Jaynes sformułował podejście oparte na maksymalnej entropii (bezpośrednie uogólnienie fizyki statystycznej) w celu rozwiązania problemów odwrotnych (w kategoriach obliczeniowych obejmują one problemy twarde )$NP$

Przegląd „ heurystyki z natury ” można znaleźć tutaj (około 95)

Inne heurystyki dotyczą uogólnionych langrangianów (inaczej algorytmy pierwotny podwójny / maksymalizacja oczekiwań)

Jednak to nie nie wyczerpują wszystkich „ heurystyki z natury ”, jak w rzeczywistości od 2003 roku nowych heurystyk opartych na electromargnetism zostały wykorzystane do przeciwdziałania zarówno ciągłych i dyskretnych / kombinatoryczne metody optymalizacji (jak wielowymiarowej plecaka , lub TSP , około 2012 roku)