Wyniki fizyki w TCS?

Wydaje się jasne, że na wiele podpól teoretycznej informatyki istotny wpływ wywarły wyniki fizyki teoretycznej. Oto dwa przykłady

1. Obliczenia kwantowe
2. Wyniki mechaniki statystycznej stosowane w analizie złożoności / algorytmach heurystycznych.

Więc moje pytanie brzmi: czy brakuje mi jakichś głównych obszarów?

Moja motywacja jest bardzo prosta: jestem fizykiem teoretycznym, który przybył do TCS za pośrednictwem informacji kwantowej i jestem ciekawy innych obszarów, w których te dwa obszary się pokrywają.

To stosunkowo miękkie pytanie, ale nie mam na myśli, że jest to pytanie typu duża lista. Szukam obszarów, w których nakładanie się jest znaczne.

Technika wyszukiwania symulowana wyżarzaniem jest inspirowana fizycznym procesem wyżarzania w metalurgii.

Wyżarzanie to obróbka cieplna, w której siła i twardość leczonej substancji może się dramatycznie zmienić. Często wiąże się to z podgrzaniem substancji do ekstremalnej temperatury, a następnie pozostawieniem jej do ostygnięcia.

Symulowane wyżarzanie pozwala uniknąć lokalnych minimów / maksimów w przestrzeniach poszukiwań poprzez włączenie stopnia losowości (temperatury) w procesie wyszukiwania. W miarę procesu wyszukiwania temperatura stopniowo się ochładza, co oznacza, że ​​ilość losowości w wyszukiwaniu maleje. Najwyraźniej jest to dość skuteczna technika wyszukiwania.

Idąc na odwrót (od TCS do fizyki), stany iloczynu macierzy, PEPS (stany projektowanych splątanych par), MERA (multnomalowa renomalizacja splątania ansatz) zostały znacząco poinformowane przez idee TCS, które zostały zaadaptowane w teorii informacji kwantowej. Te akronimy są technikami przybliżania stanów układów spinów kwantowych, które są używane przez teoretyków materii skondensowanej, aw wielu przypadkach techniki te wydają się działać lepiej niż jakiekolwiek znane wcześniej narzędzia.

Złożone systemy to dziedzina, która ma wiele wspólnego z analizą sieci społecznościowych i ogólnie sieci, i została zaatakowana przez fizyków w dużych ilościach, posługujących się bronią ze statystyki i termodynamiki. To, czy została zaatakowana przez fizykę, to inna historia.

Wynik Pour-El i Richards Adv. Matematyka 39 215 (1981) podaje istnienie niekompatybilnych rozwiązań równania falowego 3D dla obliczalnych warunków początkowych za pomocą fali do symulacji uniwersalnej maszyny Turinga.

Połączenie również działa odwrotnie. Jakiś czas temu teoretycy informatyki pracujący w teorii domen zainteresowali się względnością. Udowodnili wyniki dotyczące sposobu rekonstrukcji struktury czasoprzestrzeni ze struktury przyczynowości. Jest to coś dość znanego teoretykom domen, w którym przedmiotowymi obiektami beasycznymi są porządki częściowe, których topologia jest określona przez porządek. Możesz rzucić okiem na http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf

Bardzo starym przykładem (na który odpowiedź Suresha mogłaby przyjąć, jest to jednak inna poprawka) jest wpływ teorii sieci elektrycznych, np. Praw obwodów Kirchhoffa, na kombinatorykę, teorię grafów i prawdopodobieństwo.

Jednym z obszarów, który widział kilka aplikacji, ale niewystarczająco IMO, jest aproksymowanie dyskretnych struktur lub procesów z analitycznymi przybliżeniami. Jest to duży biznes w matematyce (np. Teorii liczb analitycznych) i fizyce (cała mechanika statystyczna), ale z jakiegoś powodu nie okazał się tak popularny w CS.

Słynne zastosowanie tego miało miejsce w projekcie maszyny łączącej. Była to masowo równoległa maszyna i jako część jej projektu musieli dowiedzieć się, jak duże są bufory w routerze. Feynman modelował router za pomocą PDE i wykazał, że bufory mogą być mniejsze niż tradycyjne argumenty indukcyjne. Danny Hillis opowiada historię w tym eseju .

Teoria mierników dla heurystycznych aproksymacji do programowania liczb całkowitych (kilka artykułów Mishy Chertkov ). Grupowe metody renormalizacji zliczania kombinatorycznego, rozdz. 10-12 „Elements of the Random Walk” Rudnicka / Gaspariego. Zastosowanie całkowego rozkładu ścieżki Feymanna (tj. Sekcja 9.5.1) do liczenia spacerów unikających siebie. W przypadku połączenia z TCS należy pamiętać, że reżim podatności na przybliżone liczenie na wykresach zależy od tempa wzrostu marszu samowystarczalnego.

Fizyka statystyczna dała informatykom nowy sposób patrzenia na SAT, tak jak to tutaj omówiono . Chodzi o to, że gdy stosunek klauzul do zmiennych biorących udział w formule 3-SAT wzrasta z około 4 do około 5, przechodzimy od możliwości rozwiązania ogromnej większości instancji 3-SAT do możliwości rozwiązania bardzo niewielu. To przejście jest traktowane jako „zmiana fazy” w SAT.

Pomysł ten zyskał szczególną popularność ubiegłego lata dzięki rzekomemu artykułowi P kontra NP Deolalikara.

Wczesna teoria systemów rozproszonych, zwłaszcza prace Lesliego Lamporta i in., Wywarły pewien wpływ ze specjalnej teorii względności, aby uzyskać prawidłowy obraz zgodny z (odporną na uszkodzenia) zgodą na globalny stan systemu. Patrz pozycja 27. ( Czas, zegary i kolejność zdarzeń w systemie rozproszonym , Komunikacja ACM 21, 7 (lipiec 1978), 558-565) w Pismach Leslie Lamport , gdzie Lamport podaje następujące informacje ogólne na temat swojego papier:

Genezą tego artykułu była notatka pt. „Utrzymanie zduplikowanych baz danych” Paula Johnsona i Boba Thomasa. Uważam, że ich notatka wprowadziła pomysł użycia znaczników czasu wiadomości w algorytmie rozproszonym. Zdarza mi się mieć solidne, trzewne zrozumienie szczególnej teorii względności (patrz [5]). Umożliwiło mi to natychmiastowe zrozumienie istoty tego, co próbowali zrobić. Szczególna teoria względności uczy nas, że nie ma niezmiennego całkowitego uporządkowania zdarzeń w czasoprzestrzeni; różni obserwatorzy mogą nie zgadzać się co do tego, które z dwóch zdarzeń miało miejsce jako pierwsze. Istnieje tylko częściowa kolejność, w której zdarzenie e1 poprzedza zdarzenie e2 iff e1 może przyczynowo wpłynąć na e2. Zrozumiałem, że esencja Johnsona i Thomasa Algorytm polegał na wykorzystaniu znaczników czasu w celu zapewnienia całkowitego uporządkowania zdarzeń, które było zgodne z porządkiem przyczynowym. Ta realizacja mogła być genialna. Uświadomiwszy to sobie, wszystko inne było banalne. Ponieważ Thomas i Johnson nie rozumieli dokładnie, co robią, algorytm nie był całkiem poprawny; ich algorytm dopuszczał anomalne zachowanie, które zasadniczo naruszało przyczynowość. Szybko napisałem krótką notatkę, wskazując na to i korygując algorytm.

Udostępniłem tę odpowiedź wraz z rozszerzoną odpowiedzią na MathOverflow na pytanie wiki Gila Kalai dotyczące społeczności „[Co to jest] Książka, którą chciałbyś napisać ”.

Rozszerzona odpowiedź ma na celu powiązanie podstawowych zagadnień w TCS i QIT z praktycznymi zagadnieniami z zakresu leczenia i medycyny regeneracyjnej.

• Geometria Josepha M. Landsberga i złożoność mnożenia macierzy (2008)

• Symplektyczna teoria Alvaro Pelayo i San Vu Ngoc całkowicie zintegrowanych układów hamiltonowskich

Matematyka dla badań Landsberga to sieczne odmiany odmian Segre , podczas gdy arena dla badań Pelayo i Ngoc to czterowymiarowe rozmaitości symplektyczne… potrzeba czasu, aby zrozumieć, że obie te areny są stanami iloczynu macierzy, patrząc odpowiednio z perspektywy obliczeniowej (Landsburg) i perspektywa geometryczna (Palayo i Ngoc). Ponadto Palayo i Ngoc uwzględniają w swojej ankiecie dyskusję na temat półklasycznego badania modelu Jaynesa-Cummingsa Babelona, ​​Cantiniego i Douçota (zauważając, że model Jaynesa-Cummingsa jest często spotykany w literaturze fizyki materii skondensowanej i obliczeń kwantowych ).

Każde z tych odniesień idzie daleko, by rozjaśnić pozostałe. W szczególności w naszych własnych (bardzo praktycznych) obliczeniach dynamiki spinowej pomocne było stwierdzenie, że kwantowe przestrzenie stanu, które są różnie opisane w literaturze jako stany sieci tensorowej, stany iloczynu macierzy i sieczne odmiany odmian Segre, są bogato wyposażone z osobliwościami, których struktura algebraiczna, symplektyczna i Riemanniana jest obecnie bardzo niezupełnie zrozumiała (jak przegląd Pelayo i Ngoc).

Dla naszych celów inżynierskich podejście Landsburga / geometrii algebraicznej , w którym przestrzeń stanu dynamiki kwantowej jest postrzegana jako różnorodność algebraiczna, a nie przestrzeń wektorowa, staje się najbardziej matematycznie naturalne. Jest to dla nas zaskakujące, ale podobnie jak wielu badaczy, stwierdzamy, że zestaw narzędzi geometrii algebraicznej jest satysfakcjonująco skuteczny w walidacji i przyspieszaniu praktycznych symulacji kwantowych.

Symulatorzy kwantowi obecnie cieszą się zagadkową okolicznością, że duże numeryczne symulacje kwantowe bardzo często działają znacznie lepiej niż mamy jakikolwiek znany powód. Gdy matematycy i fizycy dojdą do wspólnego porozumienia, ta zagadka z pewnością zmniejszy się, a przyjemność z pewnością pozostanie. Dobry! :)

Kolejnym przykładem są algorytmy rysowania wykresów oparte na sile . Chodzi o to, aby rozważyć każdą krawędź jako sprężynę, a układ węzłów wykresu odpowiada znalezieniu równowagi w zbiorze sprężyn.

Wiele matematyki, której używamy, zostało pierwotnie wymyślonych w celu rozwiązania problemów fizyki. Przykłady obejmują rachunek różniczkowy (grawitacja Newtona) i szereg Fouriera (równanie cieplne).

Istnieje niedawny artykuł, który ustanawia połączenie między Computer Security a drugą zasadą termodynamiki.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166

Pojęcie potencjału wiąże się z wieloma różnymi dziedzinami fizyki. W cs potencjał jest wykorzystywany w zamortyzowanej analizie struktur danych. Możemy spojrzeć na to, jak każdy krok wpływa na entropię systemu, a zatem uzyskać średni (zamortyzowany) koszt operacji o danej strukturze danych. Doprowadziło to do powstania wielu teoretycznie lepszych struktur danych, takich jak sterta fibonacciego.

dodać / wypełnić lukę w obecnych doskonałych odpowiedziach / pokryciu - wydaje się, że istnieje silny związek między TCS a termodynamiką na różne sposoby, które nie zostały jeszcze w pełni zbadane, ale stanowią granice aktywnych badań. istnieje punkt przejścia powiązany z SAT, ale wydaje się, że istnieją również punkty przejścia związane z innymi (lub nawet wszystkimi) klasami złożoności. punkt przejścia SAT jest związany z różnicą między instancjami „łatwymi” (P) i „twardymi” (NP), ale prawdopodobnie wszystkie granice klas złożoności muszą prowadzić do tej samej właściwości podobnej do punktu przejścia.

rozważ maszynę Turinga. już mierzy swoje działanie w normalnie fizycznych wymiarach „czasu” i „przestrzeni”. ale zauważ, że najwyraźniej wykonuje również jedną jednostkę „pracy”, przechodząc od kwadratu do kwadratu i wykonując przejście. w fizyce jednostką pracy są dżule, które są również miarą energii. wydaje się więc, że klasy złożoności mają pewien związek z poziomami energii, granicami lub reżimami.

teoria mechaniki kwantowej coraz częściej postrzega samą przestrzeń i czas, wszechświat, jako rodzaj systemu obliczeniowego. wydaje się, że ma pewne „minimalne jednostki obliczeniowe” właściwe dla jego natury, prawdopodobnie związane z długością deski. dlatego badanie minimalnych maszyn Turinga pod kątem problemów również implikuje i odnosi się do minimalnych systemów fizycznych / energetycznych lub nawet do wymaganej ilości miejsca. [3]

kluczowa koncepcja entropii pojawia się wielokrotnie w TCS i fizyce / termodynamice i może być zasadą jednoczącą, a jeszcze bardziej aktywne badania ujawniają jej zasadniczą naturę. [1,2]

[1] entropia w teorii informacji , wikipedia

[2] co to jest defnacja CS entropii , przepełnienie stosu

[3] Jaki jest wolumen informacji? tcs.se