Physikergebnisse in TCS?

Es scheint klar zu sein, dass eine Reihe von Teilbereichen der theoretischen Informatik durch Ergebnisse der theoretischen Physik erheblich beeinflusst wurden. Zwei Beispiele hierfür sind

1. Quantenberechnung
2. Ergebnisse der statistischen Mechanik für Komplexitätsanalysen / heuristische Algorithmen.

Meine Frage ist also, ob ich wichtige Bereiche vermisse.

Meine Motivation ist sehr einfach: Ich bin ein theoretischer Physiker, der über Quanteninformationen zur TCS gekommen ist, und ich bin neugierig auf andere Bereiche, in denen sich die beiden Bereiche überschneiden.

Dies ist eine relativ weiche Frage, aber ich meine nicht, dass dies eine Frage vom Typ einer großen Liste ist. Ich suche nach Bereichen, in denen die Überlappung erheblich ist.

Die Suchtechnik des simulierten Glühens ist vom physikalischen Prozess des Glühens in der Metallurgie inspiriert .

Das Tempern ist eine Wärmebehandlung, bei der sich Stärke und Härte des zu behandelnden Stoffes dramatisch ändern können. Häufig wird dabei die Substanz auf eine extreme Temperatur erhitzt und dann langsam abkühlen gelassen.

Durch simuliertes Tempern werden lokale Minima / Maxima in Suchräumen vermieden, indem ein Grad an Zufälligkeit (die Temperatur) in den Suchprozess einbezogen wird. Mit fortschreitendem Suchvorgang kühlt sich die Temperatur allmählich ab, was bedeutet, dass die Zufälligkeit bei der Suche abnimmt. Anscheinend ist es eine ziemlich effektive Suchtechnik.

Umgekehrt (von TCS zu Physik) wurden Matrixproduktzustände, PEPS (Projected Entangle Pair States) und MERA (Multiscale Entanglement Renomalization Ansatz) maßgeblich durch TCS-Ideen beeinflusst, die in der Quanteninformationstheorie adaptiert wurden. Diese Akronyme sind alle Techniken zur Approximation der Zustände von Quantenspinsystemen, die von Theoretikern der kondensierten Materie verwendet werden, und in vielen Fällen scheinen diese Techniken besser zu funktionieren als alle bisher bekannten Werkzeuge.

Komplexe Systeme sind ein Bereich, der viel mit der Analyse sozialer Netzwerke und Netzwerken im Allgemeinen zu tun hat und in dem Physiker in großer Zahl mit Waffen aus Statistik und Thermodynamik eingedrungen sind. Ob es von der Physik angegriffen wurde, ist eine andere Geschichte.

Ein Ergebnis von Pour-El und Richards Adv. Mathematik. 39 215 (1981) gibt die Existenz nicht berechenbarer Lösungen der 3D-Wellengleichung für berechenbare Anfangsbedingungen an, indem die Welle zur Simulation einer universellen Turingmaschine verwendet wird.

Die Verbindung ist auch umgekehrt. Vor einiger Zeit interessierten sich theoretische Informatiker, die in der Domänentheorie arbeiten, für die Relativitätstheorie. Sie zeigten Ergebnisse darüber, wie die Struktur der Raumzeit aus der Kausalitätsstruktur rekonstruiert werden kann. Dies ist Domänen-Theoretikern recht vertraut, bei denen es sich bei den interessierenden Beasic-Objekten um Teilordnungen handelt, deren Topologie durch die Reihenfolge bestimmt wird. Sie könnten einen Blick auf http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf werfen

Ein sehr altes Beispiel (das mit Sureshs Antwort zusammengefasst werden könnte, dies ist jedoch eine andere Wendung) ist der Einfluss der Theorie elektrischer Netze, z. B. Kirchhoffs Schaltungsgesetze, auf die Kombinatorik, die Graphentheorie und die Wahrscheinlichkeit.

Ein Bereich, in dem einige Anwendungen, aber nicht IMO-genug, aufgetreten sind, ist die Approximation diskreter Strukturen oder Prozesse mit analytischen Approximationen. Dies ist ein großes Geschäft in Mathematik (z. B. analytische Zahlentheorie) und Physik (alle statistische Mechanik), hat sich aber aus irgendeinem Grund in CS nicht als beliebt erwiesen.

Eine berühmte Anwendung davon war das Design der Connection Machine. Dies war eine sehr parallele Maschine, und als Teil ihres Designs müssen sie herausfinden, wie groß die Puffer im Router sind. Feynman modellierte den Router mit PDEs und zeigte, dass die Puffer kleiner sein könnten als die traditionellen induktiven Argumente. Danny Hillis erzählt die Geschichte in diesem Aufsatz .

Maßtheorie für heuristische Annäherungen an die Ganzzahlprogrammierung (einige Arbeiten von Mischa Tschertkow ). Renormalisierungsgruppenmethoden für das kombinatorische Zählen, Kapitel 10-12 von Rudnick / Gasparis "Elements of the Random Walk". Anwenden der Feymannschen Pfadintegralzerlegung (dh Abschnitt 9.5.1) auf das Zählen von selbstvermeidenden Spaziergängen. Beachten Sie für die Verbindung mit TCS, dass das Traktabilitätsregime für die ungefähre Zählung in Diagrammen von der Wachstumsrate von selbstvermeidenden Wanderungen abhängt.

Die statistische Physik hat den Informatikern eine neuartige Sichtweise auf SAT eröffnet, wie hier dargestellt . Die Idee ist, dass mit zunehmendem Verhältnis von Klauseln zu Variablen in einer 3-SAT-Formel von ungefähr 4 auf ungefähr 5 die überwiegende Mehrheit der 3-SAT-Instanzen gelöst werden kann und nur sehr wenige gelöst werden können. Dieser Übergang wird in SAT als "Phasenwechsel" angesehen.

Diese Idee erlangte im vergangenen Sommer besondere Bekanntheit durch Deolalikars angebliches P vs. NP-Papier.

Die frühe Theorie der verteilten Systeme, insbesondere die Arbeiten von Leslie Lamport et al., Hat einige Auswirkungen auf die Spezifische Relativitätstheorie gehabt, um das richtige Bild für eine (fehlertolerante) Einigung über einen globalen Systemzustand zu erhalten. Siehe Eintrag 27. ( Zeit, Uhren und die Reihenfolge von Ereignissen in einem verteilten System , Mitteilungen der ACM 21, 7 (Juli 1978), 558-565) in den Schriften von Leslie Lamport , in denen Lamport die folgenden Hintergrundinformationen über seine Papier:

Der Ursprung dieses Papiers war eine Notiz mit dem Titel The Maintenance of Duplicate Databases von Paul Johnson und Bob Thomas. Ich glaube, ihre Notiz führte die Idee ein, Nachrichtenzeitstempel in einem verteilten Algorithmus zu verwenden. Ich habe zufällig ein solides, viszerales Verständnis für die spezielle Relativitätstheorie (siehe [5]). Dies ermöglichte es mir, sofort die Essenz dessen zu erfassen, was sie zu tun versuchten. Die spezielle Relativitätstheorie lehrt uns, dass es keine invariante Gesamtordnung von Ereignissen in der Raumzeit gibt; Verschiedene Beobachter können sich nicht darüber einig sein, welches der beiden Ereignisse zuerst stattgefunden hat. Es gibt nur eine Teilreihenfolge, in der ein Ereignis e1 einem Ereignis e2 vorausgeht, wenn e1 e2 kausal beeinflussen kann. Ich erkannte, dass die Essenz von Johnson und Thomas Bei diesem Algorithmus wurden Zeitstempel verwendet, um eine vollständige Reihenfolge der Ereignisse zu erhalten, die mit der kausalen Reihenfolge übereinstimmt. Diese Erkenntnis mag brillant gewesen sein. Alles andere war trivial. Da Thomas und Johnson nicht genau verstanden, was sie taten, haben sie den Algorithmus nicht richtig verstanden. Ihr Algorithmus erlaubte anomales Verhalten, das im Wesentlichen gegen die Kausalität verstieß. Ich schrieb schnell eine kurze Notiz, in der ich darauf hinwies und den Algorithmus korrigierte.

Ich habe diese Antwort mit einer erweiterten Antwort auf MathOverflow auf Gil Kalais Wiki-Frage "[Was ist] ein Buch, das du gerne schreiben würdest? "

Die erweiterte Antwort versucht, grundlegende Fragen in Bezug auf TCS und QIT mit praktischen Fragen in Bezug auf Heilung und regenerative Medizin zu verknüpfen.

• Joseph M. Landsbergs Geometrie und die Komplexität der Matrixmultiplikation (2008)

• Alvaro Pelayos und San Vu Ngocs symplektische Theorie vollständig integrierbarer Hamilton-Systeme

Die mathematische Arena für Landsbergs Vermessung sind Sekantenvarianten von Segre-Sorten , während die Arena für Pelayos und Ngocs Vermessung vierdimensionale symplektische Mannigfaltigkeiten sind (Landsburg) und eine geometrische Perspektive (Palayo und Ngoc). Darüber hinaus nehmen Palayo und Ngoc in ihre Umfrage eine Diskussion über Babelon, Cantini und Douçots Eine halbklassische Studie des Jaynes-Cummings-Modells auf (wobei festgestellt wird, dass das Jaynes-Cummings-Modell in der Literatur der Festkörperphysik und des Quantencomputers häufig anzutreffen ist ).

Jede dieser Referenzen geht weit, um die anderen zu erhellen. Insbesondere hat es sich in unseren eigenen (sehr praktischen) spindynamischen Berechnungen als hilfreich erwiesen, zu erkennen, dass die Quantenzustandsräume, die in der Literatur als Tensornetzzustände, Matrixproduktzustände und Sekantensorten von Segre-Sorten unterschiedlich beschrieben werden, reich dotiert sind mit Singularitäten, deren algebraische, symplektische und Riemannsche Struktur derzeit sehr unvollständig verstanden wird (als Pelayo und Ngoc Review).

Für unsere technischen Zwecke ist der Ansatz der Landsburger / algebraischen Geometrie , bei dem der Zustandsraum der Quantendynamik als algebraische Variante und nicht als Vektorraum betrachtet wird, der mathematisch natürlichste. Dies ist für uns überraschend, aber gemeinsam mit vielen Forschern stellen wir fest, dass das Toolset der algebraischen Geometrie bei der Validierung und Beschleunigung praktischer Quantensimulationen erfreulich wirksam ist.

Quantensimulatoren erfreuen sich derzeit des rätselhaften Umstands, dass große numerische Quantensimulationen sehr oft eine viel bessere Leistung erbringen, als wir es aus irgendeinem bekannten Grund erwarten können. Wenn Mathematiker und Physiker zu einem gemeinsamen Verständnis gelangen, wird diese Verwirrung mit Sicherheit nachlassen und der Genuss wird mit Sicherheit bestehen bleiben. Gut! :)

Ein weiteres Beispiel sind kraftbasierte Algorithmen zum Zeichnen von Graphen . Die Idee ist, jede Kante als eine Feder zu betrachten und die Anordnung der Knoten des Graphen entspricht dem Finden des Gleichgewichts in der Sammlung von Federn.

Ein Großteil der Mathematik, die wir verwenden, wurde ursprünglich erfunden, um physikalische Probleme zu lösen. Beispiele hierfür sind Kalkül (Newtonsche Schwerkraft) und Fourierreihen (Wärmegleichung).

Es gibt eine kürzlich erschienene Veröffentlichung, die die Verbindung zwischen Computersicherheit und dem 2. Prinzip der Thermodynamik herstellt.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166

Das Konzept des Potenzials bezieht sich auf viele verschiedene Bereiche der Physik. In cs wird Potenzial für die amortisierte Analyse von Datenstrukturen genutzt. Wir können untersuchen, wie sich jeder Schritt auf die Entropie des Systems auswirkt, und daher die durchschnittlichen (amortisierten) Kosten einer Operation mit einer bestimmten Datenstruktur ermitteln. Dies hat zu vielen theoretisch besseren Datenstrukturen wie dem Fibonacci-Heap geführt.

um eine Lücke in den aktuellen exzellenten Antworten / Berichten zu schließen - es scheint eine enge Verbindung zwischen TCS und Thermodynamik in verschiedener Hinsicht zu geben, die noch nicht vollständig erforscht wurde, aber die Grenzen aktiver Forschung darstellt. Es gibt einen Übergangspunkt, der mit SAT verbunden ist, aber möglicherweise gibt es auch Übergangspunkte, die mit anderen (oder sogar allen) Komplexitätsklassen verbunden sind. Der SAT-Übergangspunkt ist mit einem Unterschied zwischen "einfachen" (P) und "harten" (NP) Instanzen verbunden, aber wohl müssen alle Komplexitätsklassengrenzen zu derselben übergangspunktartigen Eigenschaft führen.

Betrachten Sie eine Turing-Maschine. es misst bereits seinen Betrieb in normalerweise physikalischen Dimensionen von "Zeit" und "Raum". Beachten Sie jedoch, dass es anscheinend auch eine Einheit "Arbeit" leistet, indem es von Quadrat zu Quadrat wechselt und einen Übergang durchführt. In der Physik ist die Arbeitseinheit Joules, was auch ein Maß für die Energie ist. Es scheint also, dass Komplexitätsklassen einen gewissen Bezug zu Energieniveaus, Grenzen oder Regimen haben.

Die Theorie der Quantenmechanik sieht Raum und Zeit selbst, das Universum, zunehmend als eine Art Computersystem. es scheint, dass es einige "minimale Recheneinheiten" hat, die seiner Natur eigen sind und wahrscheinlich mit der Länge der Planke zusammenhängen. Daher impliziert und bezieht sich die Prüfung von Turing-Maschinen auf minimale Probleme auch auf minimale physische / energetische Systeme oder sogar auf das erforderliche Raumvolumen. [3]

Der Schlüsselbegriff der Entropie taucht auch wiederholt in TCS und Physik / Thermodynamik auf und könnte ein verbindendes Prinzip mit noch aktiverer Forschung sein, die seine zugrunde liegende Natur aufdeckt. [1,2]

[1] Entropie in der Informationstheorie , Wikipedia

[2] Was ist die CS Defn der Entropie , Stackoverflow

[3] Wie groß ist das Informationsvolumen? tcs.se