Interesuje mnie nauka powiązań między „chaosem”, a szerzej, systemami dynamicznymi, a pytaniem . Oto przykład rodzaju literatury, której szukam:
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?
cc.complexity-theory
p-vs-np
Joseph O'Rourke
źródło
źródło
Odpowiedzi:
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]
[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
źródło
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
źródło
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 ( ≈αre αdo ≈ 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).
źródło
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.
źródło