Chaos i pytanie

Interesuje mnie nauka powiązań między „chaosem”, a szerzej, systemami dynamicznymi, a pytaniem . Oto przykład rodzaju literatury, której szukam:$P{=}NP$

Ercsey-Ravasz, Mária i Zoltán Toroczkai. „Twardość optymalizacji jako przejściowy chaos w analogicznym podejściu do satysfakcji z ograniczeń”. Nature Physics 7, no. 12 (2011): 966–970. ( Link do czasopisma ).

Czy ktoś napisał ankietę lub stworzył kompendium bibliograficzne?

artykuł cytowany przez Ercsey-Ravasz, Toroczkaijest bardzo przekrojowy; pasuje do / dotyka kilku linii kompletnego badania problemu / złożoności / twardości NP. związek z fizyką statystyczną i szkłami obrotowymi odkryto głównie poprzez „przejścia fazowe” w połowie lat 90. XX wieku, co doprowadziło do dużego nakładu pracy, patrz Gogioso [1] dla badania 56p. przejście fazowe pokrywa się z tak zwanym „ostrzem noża ograniczenia” w [2]. dokładnie ten sam punkt przejścia pojawia się w bardzo teoretycznych analizach złożoności obliczeniowej / twardości, np. [3], które również odnoszą się do wczesnych badań zachowania punktu przejścia w problemach kliki autorstwa Erdosa. [4] to ankieta / wykład wideo na temat przejść fazowych i złożoności obliczeniowej autorstwa Moshe Vardi. [5] [6] to przegląd zachowań związanych z przejściem fazowym między kompletnymi problemami NP przez Moore, Walsh.

następnie rozproszone, ale być może coraz większe badanie różnorodnych połączeń układów dynamicznych o złożoności obliczeniowej i twardości w różnych kontekstach. istnieje ogólny związek znaleziony w [7], prawdopodobnie wyjaśniający niektóre podstawowe przyczyny częstego „nakładania się”. refs [8] [9] [10] [11] są różnorodne, ale wykazują ponowny motyw / wygląd przekroju między kompletnymi problemami NP i różnymi układami dynamicznymi. w tych pracach jest kilka koncepcji / przykładów hybrydowego połączenia między systemami dyskretnymi i ciągłymi.

chaotyczne zachowanie w kompletnych systemach NP jest analizowane w [11].

Nieco podobne odniesienie do Ercsey-Ravasz / Toroczkai w dziedzinie algorytmów kwantowych, ponieważ stwierdzono, że układ dynamiczny działa „pozornie” w czasie P [12]

W tym artykule badamy nowe podejście do algorytmu kwantowego, które jest kombinacją zwykłego algorytmu kwantowego z chaotycznym układem dynamicznym. Traktujemy problem satysfakcji jako przykład problemów NP-zupełnych i twierdzimy, że problem ten można zasadniczo rozwiązać w czasie wielomianowym za pomocą naszego nowego algorytmu kwantowego.

[1] Aspekty fizyki statystycznej w złożoności obliczeniowej / Gogioso

[2] Ostrze noża ograniczającego / Toby Walsh

[3] Monotoniczna złożoność k-Clique na Random Graphs / Rossman

[4] Przejścia fazowe i złożoność obliczeniowa / Moshe Vardi

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

[6] Zachowanie przejścia fazowego / Walsh

[7] Wyznaczanie równań dynamicznych jest trudne / Cubitt, Eisert, Wolf

[8] Problem z układem w stanie ustalonym jest trudny dla NP, nawet dla monotonicznych kwadratowych logicznych układów dynamicznych / Just

[9] Problemy istnienia poprzednika i permutacji dla sekwencyjnych układów dynamicznych / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (dotyczy także problemów z analizą dla graficznych układów dynamicznych: ujednolicone podejście poprzez predykaty grafowe )

[10] Podejście systemów dynamicznych do dopasowywania wykresów ważonych / Zavlanos, Pappas

[11] O chaotycznym zachowaniu niektórych problemów np. Zupełnych / Perl

[12] Nowy algorytm kwantowy do badania problemów NP-zupełnych / Ohya, Volovich

Istnieje stosunkowo nowy trend badawczy (około 15 lat) mieszania fizyki statystycznej układów nieuporządkowanych z dyskretnymi, kombinatorycznymi problemami optymalizacji. Powiązanie odbywa się za pomocą prawdopodobieństw Boltzmanna, a twardość obliczeniowa jest związana z zwielokrotnieniem stanów metastabilnych układu fizycznego. Modele okularów obrotowych można udowodnić, że są izomorficzne dla większości dyskretnych problemów związanych z optymalizacją.

Radzę zacząć od pracy doktorskiej, tam znajdziesz więcej referencji

Lenka Zdeborová. Fizyka statystyczna problemów trudnej optymalizacji na stronie http://arxiv.org/abs/0806.4112

Klasyczny artykuł, który, szczerze mówiąc, nie rozumiem tak dobrze, to:

David L. Donoho, Jared Tanner. Obserwowana uniwersalność przejść fazowych w geometrii wielowymiarowej z implikacjami dla nowoczesnej analizy danych i przetwarzania sygnałów na stronie http://arxiv.org/abs/0906.2530

Ponadto na temat szklanek obrotowych wprowadzenie

Tommaso Castellani, Andrea Cavagna. Teoria spin-szkła dla pieszych

Niestety znajduje się za ścianą płatniczą, więc nie jestem w stanie wyświetlić tego artykułu, ale po przeczytaniu streszczenia wykazuje on przynajmniej powierzchowne podobieństwo do niektórych „kreskówkowych zdjęć”, które widziałem podczas propagacji badań i służy do rozwiązania 3-SAT. Oto „obraz animowany” z „Nowego spojrzenia na propagowanie badań i jego uogólnienia” autorstwa Manevy, Mossela i Wainwrighta

Tutaj ma wartość przejścia gęstości i α C jest krytyczna wartość progowa ( $\alpha_d$$\alpha_c$$\approx 4.2$

Ciekawie byłoby sprawdzić, czy lokalizacje różnych regionów fraktalnych zgłoszone przez Ercsey-Ravasz i Toroczkai odpowiadają różnym progom krytycznym zauważonym w propagowaniu badań (lub jeśli się mylę, a podobieństwo jest naprawdę powierzchowne).

Ten artykuł, rozwiązanie wielomianowego czasowego rozkładania na czynniki pierwsze i problemów z całkowitą NP z cyfrowymi urządzeniami do przetwarzania danych, twierdzi, że jest wydajnym algorytmem dla problemów z całkowitą NP. Cyfrowe maszyny obliczeniowe to nieliniowe układy dynamiczne zaprojektowane w taki sposób, aby ich punkty równowagi odpowiadały rozwiązaniom logicznego problemu satysfakcji. Najważniejszą implikacją jest to, że może istnieć dynamiczny system, który skutecznie rozwiązuje problemy z NP. Wnioskują, że ich wynik nie rozwiązuje jeszcze problemu P vs NP. P = NP wynikałoby z formalnego udowodnienia, że ​​jeśli równowaga istnieje, globalny atraktor nie obsługuje okresowych orbit i / lub dziwnych atraktorów.

Odniesienie:

1- Traversa i Di Ventra, Wielomianowe rozwiązanie rozkładania na czynniki pierwsze i problemy NP-zupełne z cyfrowymi urządzeniami do przetwarzania danych , Chaos: An Interdisciplinary Journal of Nonlinear Science, Tom 27, Wydanie 2, 2017

2- Traversa, Ramella, Bonani i Di Ventra, Memcomputing NP-zupełne problemy w czasie wielomianowym z wykorzystaniem zasobów wielomianowych i stanów zbiorowych , Science Advances, Tom 1, wydanie 6, 2015.