Algorithmen und strukturelle Komplexitätstheorie

21

Viele wichtige Ergebnisse in der rechnerischen Komplexitätstheorie und insbesondere in der "strukturellen" Komplexitätstheorie haben die interessante Eigenschaft, dass sie aus algorithmischen Ergebnissen, die für einige einen effizienten Algorithmus oder ein effizientes Kommunikationsprotokoll liefern, als grundlegend zu verstehen sind (wie ich es sehe ...) Problem. Dazu gehören die folgenden:

  • IP = PSPACE ergibt sich aus einem platzsparenden rekursiven Algorithmus, der interaktive Protokolle simuliert, und einem effizienten interaktiven Protokoll zur Auswertung vollständig quantifizierter Boolescher Formeln. Tatsächlich kann jede Komplexitätsklassengleichheit A = B aus zwei effizienten Algorithmen (einem Algorithmus für Probleme in A, der in Bezug auf B effizient ist, und umgekehrt) als folgt angesehen werden.
  • Der Nachweis der NP-Vollständigkeit eines Problems besteht darin, einen effizienten Algorithmus zu finden, um ein NP-vollständiges Problem auf dieses zu reduzieren.
  • Der (wohl!) Entscheidende Bestandteil des Zeithierarchiesatzes ist eine effiziente universelle Simulation von Turingmaschinen.
  • Das jüngste Ergebnis von Ryan Williams, dass ACC NEXP auf einem effizienten Algorithmus basiert, um die Schaltungserfüllbarkeit für ACC-Schaltungen zu lösen.
  • Das PCP-Theorem besagt, dass eine effiziente Lückenverstärkung für Bedingungserfüllungsprobleme möglich ist.
  • usw. usw.

Meine Frage (die möglicherweise hoffnungslos vage ist!) Lautet wie folgt: Gibt es wichtige Ergebnisse in der strukturellen Komplexitätstheorie (im Unterschied zu "Metaergebnissen" wie der Relativierungsbarriere), von denen nicht bekannt ist, dass sie eine natürliche Interpretation in Bezug auf Effizienz haben? Algorithmen (oder Kommunikationsprotokolle)?

Ashley Montanaro
quelle
8
Ich Art von Hoffnung ist die Antwort „nein“ , weil ich denke , Komplexität ist wirklich über die Macht der Algorithmen zu verstehen! Ich wollte sagen, dass PARITÄT nicht in fast qualifiziert, aber jetzt denke ich nicht so. Sie können die Schalt Lemma als randomisierten Algorithmus anzeigen , die Sie ohne große Größe Blow-up tauschen zwei Reihen einer Schaltung können (und es sogar derandomisiert werden kann ( eccc.hpi-web.de/report/2012/116 ).AC0
Joshua Grochow
2
AshleyMontanaro: Vielleicht hängt die Komplexitätstheorie "per Definition" mit der (zeitlichen / räumlichen) Effizienz der Algorithmen zusammen. Sobald Sie sich von der Effizienz entfernen, finden Sie grundlegende Ergebnisse wie die Unentscheidbarkeit des Stopp-Problems, aber Sie befinden sich nicht mehr im Bereich "Komplexität". Ich denke jedoch, dass die logische Charakterisierung von Komplexitätsklassen ein wichtiges Ergebnis ist, das eine andere Perspektive bietet, die nicht (direkt) an "Algorithmen" gebunden ist.
Marzio De Biasi
3
Insbesondere hätte ich die beschreibende Charakterisierung von NP in Bezug auf existentielle Logik zweiter Ordnung aufgelistet. Hier geht es nur um Ausdruckskraft und nicht in erster Linie um Algorithmen. Der Satz von Courcelle legt jedoch nahe, dass diese Unterscheidung nicht real ist.
Suresh Venkat
3
Würden Sie sagen, dass der Razborov-Smolensky-PARITÄTSnachweis, der nicht in AC0 enthalten ist, im Kern ein algorithmisches Ergebnis enthält? Und wie steht es mit den unteren Grenzen der Abfragekomplexität, die laut Aussage eines Quantencomputers das ungeordnete Suchproblem in Abfragen nicht lösen können ? o(n)
Robin Kothari

Antworten:

19

Für viele untere Schranken der algebraischen Komplexität kenne ich keine natürliche Interpretation hinsichtlich effizienter Algorithmen. Beispielsweise:

  • die partielle Ableitungstechnik von Nisan und Wigderson

  • die Rang-von-Hessian-Technik von Mignon und Ressayre (die derzeit bekannteste untere Schranke für permanente versus Determinante)

  • der Grad gebunden von Strassen (und Baur-Strassen)

  • die verbundene Komponententechnik von Ben-Or.

In all den obigen Ergebnissen scheinen sie tatsächlich eine Eigenschaft der beteiligten Funktionen zu verwenden, wobei diese Eigenschaft selbst nicht mit der Existenz eines bestimmten Algorithmus (geschweige denn eines effektiven) in Zusammenhang zu stehen scheint.

Für nicht-algebraische Ergebnisse sind hier einige Gedanken:

  • Das Standard-Zählargument für die untere Grenze der Sortierung scheint keine Interpretation in Bezug auf effiziente Algorithmen zu haben. Es gibt jedoch eine kontroverse Version dieser Untergrenze [1], in der es einen Algorithmus gibt, der bei einem Entscheidungsbaum, der zu wenige Vergleiche verwendet, effizient eine Liste erstellt, die der Entscheidungsbaum falsch sortiert. Die gegnerische Version ist zwar nicht schwierig, aber deutlich schwieriger als der Zählnachweis. (Beachten Sie, dass dies viel stärker ist als das, was man durch Anwendung der Technik der unteren Grenze des Gegners erhält, z. B. wie in diesen Anmerkungen , da in [1] der Gegner selbst effizient ist .)nLogn

  • Ich denke, ich habe meine Meinung über PARITÄT geändert, nicht in (sogar der Originalbeweis, geschweige denn der von @RobinKothari erwähnte Razborov-Smolensky-Beweis). Obwohl das Umschalt-Lemma als zufälliger ( oder deterministischer ) Algorithmus angesehen werden kann, mit dem Sie zwei Zeilen eines Stromkreises vertauschen können, ohne dass dies zu einer großen Vergrößerung führt, denke ich, dass dies einen anderen Geschmack hat als viele Komplexitätsergebnisse, insbesondere der diejenigen, die du zitierst. Williams 'Beweis, dass entscheidender ist, basiert auf der Existenz eines guten Algorithmus für ein bestimmtes Problem. Wenn man dagegen etwas wie das Switching-Lemma nicht konstruktiv beweisen könnte, wäre es genauso gut, um die PARITÄT nicht in zu beweisen . A C C N E X P A C 0EINC0EINCCNEXPEINC0

Aufgrund dieser beiden letzten Beispiele - insbesondere der Sortierung, bei der der Standardbeweis nicht konstruktiv ist - scheint mir die Frage nicht nur nach natürlichen Interpretationen im Hinblick auf effiziente Algorithmen zu lauten, sondern auch nach der Konstruktivität / Wirksamkeit der Beweise verschiedener Komplexität resultiert (abhängig davon, was das OP im Sinn hatte). Das heißt, die untere Grenze der Standardsortierung ist nicht konstruktiv oder algorithmisch, aber es gibt einen konstruktiven, algorithmischen Beweis für dasselbe Ergebnis.

[1] Atallah, MJ und Kosaraju, SR Eine gegnerische Untergrenze zum Sortieren . Informieren. Proc. Lette. 13 (2): 55-57, 1981.

Joshua Grochow
quelle