Wichtigste neue Arbeiten in rechnerischer Komplexität

Wir hören oft von klassischen Forschungen und Veröffentlichungen auf dem Gebiet der rechnerischen Komplexität (Turing, Cook, Karp, Hartmanis, Razborov usw.). Ich habe mich gefragt, ob es kürzlich veröffentlichte Artikel gibt, die als wegweisend gelten und gelesen werden müssen. Mit neu meine ich in den letzten 5/10 Jahren.

Die jüngste Veröffentlichung von László Babai, die zeigt, dass der Graphisomorphismus in Quasi-P vorliegt, ist bereits ein Klassiker.

Hier finden Sie eine zugänglichere Darstellung des Ergebnisses, das im ICM 2018 veröffentlicht wurde.

In einem kürzlich erschienenen Preprint zeigen Harvey und Van Der Hoeven, wie die ganzzahlige Multiplikation in Zeit$O(n \log n)$ auf einer Multi-Tape-Turing-Maschine berechnet wird. Fürer, Harvey-Van Der Hoeven-Lecerf). Das Papier wurde noch nicht von Experten begutachtet, aber frühere Arbeiten der Autoren zu diesem Problem machen es plausibel, und Experten scheinen optimistisch zu sein.

Die Bedeutung ist in den Augen des Betrachters. Ich würde jedoch sagen, dass die von A. Bulatov und D. Zhuk unabhängig bewiesene Feder-Vardi-CSP-Dichotomie-Vermutung ein wegweisendes Ergebnis ist.

Uneinheitliche ACC Circuit Lower Bounds von Ryan Williams:

https://people.csail.mit.edu/rrw/acc-lbs.pdf

und klassische Verifikation von Quantenberechnungen von Urmila Mahadev:

http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf

scheinen wie gute Kandidaten

Diese neue Veröffentlichung von Hao Huang [1] (meines Wissens noch nicht von Fachleuten begutachtet) ist wahrscheinlich ein Beweis für die seit ca. 30 Jahren bestehende Sensitivitätsvermutung von Nisan und Szegedy.

[1] Induzierte Untergraphen von Hyperwürfeln und ein Beweis für die Sensitivitätsvermutung, Hao Huang. Manuskript, 2019. https://arxiv.org/abs/1907.00847

Subhash Khot, Dor Minzer und Muli Safras 2018 erschienene Arbeit "Pseudozufallssätze in Grassmann Graph haben eine nahezu perfekte Ausdehnung" hat uns "auf halbem Wege" zur " Unique Games Conjecture" gebracht und ist methodisch für Leute interessanter als ich. Zitat von Boaz Barak ,

Dies legt zum ersten Mal die Härte von einzigartigen Spielen in dem Regime fest, für das ein subexponentieller Zeitalgorithmus bekannt war, und verwendet daher (notwendigerweise) eine Reduktion mit einem gewissen (großen) Polynom-Blowup. Während es theoretisch immer noch möglich ist, dass die Vermutung eines einzigartigen Spiels falsch ist (wie ich persönlich bis zu dieser letzten Folge von Ergebnissen geglaubt habe), ist das wahrscheinlichste Szenario jetzt, dass die UGC wahr ist, und die Komplexität der UG (s) , c) Problem sieht ungefähr so ​​aus ...

Das Papier hat einige Forscher (einschließlich Barak) veranlasst, ihre Meinung über die Wahrheit der UGC öffentlich zu ändern (von falsch zu wahr).

"Über die Möglichkeit schnellerer SAT-Algorithmen" von Pătraşcu & Williams (SODA 2010). Es gibt enge Beziehungen zwischen der Komplexität der Lösung von CNF-SAT und der Komplexität einiger Polynomprobleme (k-dominierende Menge, d-Summe usw.).

Die Ergebnisse sind zweifach: Entweder können wir die Komplexität der Lösung einiger Polynomprobleme verbessern, und daher ist ETH falsch und wir erhalten einen besseren Algorithmus für CNF-SAT. Oder die ETH ist wahr, und so erhalten wir untere Schranken für mehrere Polynomprobleme.

Das Papier ist überraschend leicht zu lesen und zu verstehen. Für mich ist es der eigentliche Beginn einer feinkörnigen Komplexität.

Es ist ein Jahr nach dem Zehnjahreslimit, aber „Delegieren von Berechnungen: Interaktive Beweise für Muggel“ von Goldwasser, Kalai und Rothblum war ein äußerst einflussreiches Papier. Das Hauptergebnis ist, dass es einen interaktiven Beweis für jede einheitliche Berechnung des Protokollraums gibt, bei der der Bestätiger in der Zeit poly (n) und der Prüfer in der Zeit n * polylog (n) mit polylog (n) Kommunikationsbits läuft.

Die Arbeit hat die Erforschung interaktiver Beweise vorangetrieben, und die überprüfbare Berechnung von Problemen in P war in der Kryptographie unglaublich einflussreich, wo es und die anschließende Arbeit dazu geführt hat, dass reale interaktive Beweise nahezu praktisch waren.

Für Auswirkungen und Reichweite Wahrzeichen Papiere von Indyk und Backurs Grenzen zu bearbeiten Entfernungsberechnung geben. In diesem Artikel werden die Grenzen des Rechnens durch Verknüpfung von k-SAT und SETH aufgezeigt. Um die Berechnung des Abstandes zwischen den Zeichenfolgen zu begrenzen, weist das Papier enge Grenzen für die Berechnung des Bearbeitungsabstandes auf - besser, als SETH verletzt wird (SETH kann an erster Stelle falsch sein oder sogar engere untere Grenzen aufweisen ). Die Anwendbarkeit von SETH auf mögliche Probleme in P, das Erhalten von Grenzen oder die Einschränkung der Anwendung von Algorithmen (möglicherweise Berechnung!) Ist neu.

Oder diese Arbeit von P. Goldberg und C. Papadimitrou über eine einheitliche Komplexität für Gesamtfunktionen Hin zu einer einheitlichen Komplexitätstheorie für Gesamtfunktionen .

Ich bin mir nicht sicher, ob dies in Frage kommt - beide sind älter als 10 Jahre und es ergibt sich keine wirkliche rechnerische Komplexität -, aber ich denke, das Paar {Graph Structure Theorem, Graph Minor Theorem} ist erwähnenswert. Es wurde 2004 fertiggestellt und stellt eine Äquivalenz zwischen "Begrenzte topologische Komplexität" und "Enthält keine endlichen Mengen von Minderjährigen" her. Jeder Satz legt eine Richtung der Äquivalenz fest.

Dies hat sich vor allem im Bereich der parametrisierten Komplexitätstheorie ausgewirkt, bei der eine dieser Kennzahlen häufig begrenzt ist und effiziente Algorithmen ermöglicht, die die andere nutzen. Ich würde also sagen, dass diese Ergebnisse einen erheblichen Einfluss auf die Komplexität der Berechnungen hatten, auch wenn sie nicht direkt aus diesem Bereich stammen.