Beweise, dass PPAD schwer ist?

32

Es gibt oft zitierte philosophische Rechtfertigungen für die Annahme, dass P! = NP auch ohne Beweise ist. Andere Komplexitätsklassen weisen auf ihre Unterscheidbarkeit hin, da sich sonst "überraschende" Konsequenzen ergeben würden (wie der Zusammenbruch der Polynomhierarchie).

Meine Frage ist, was ist die Grundlage für die Annahme, dass die Klasse PPAD unlösbar ist? Wenn es einen polynomiellen Zeitalgorithmus zum Auffinden von Nash-Gleichgewichten gäbe, würde dies etwas über andere Komplexitätsklassen bedeuten? Gibt es ein heuristisches Argument dafür, warum es schwierig sein sollte?

Aaron Roth
quelle

Antworten:

28

PPAD ist ziemlich "niedrig" über P und es würde sich in unserem Verständnis der Komplexität nicht viel ändern, wenn es gleich P gezeigt würde (außer dass die wenigen Probleme in PPAD jetzt in P wären). Der wichtigste "Beweis", dass PPAD! = P eine Orakeltrennung ist, entspricht im Wesentlichen der kombinatorischen Tatsache, dass keine "Black-Box-Simulation" existiert.

Noam
quelle
8

Buhrman et al. Es hat sich gezeigt, dass es ein Orakel gibt, zu dem alle TFNP-Funktionen mehrmals berechenbar sind, die Polynom-Hierarchie jedoch unendlich ist. TFNP ist eine Klasse, die PPAD und seine Cousins ​​enthält. Dies ist ein weiteres Ergebnis, das unser Gefühl stärkt, dass eine einfache PPAD keine unwahrscheinlichen Folgen für die Komplexität haben würde.

Der Artikel lautet: "Bricht die Polynom-Hierarchie zusammen, wenn die Funktionen invertierbar sind?"

auf der Website von Lance Fortnow verfügbar. Es scheint, dass eine frühere Version des Papiers den Titel "Invertieren in Funktionen und die Polynomhierarchie" trug (die neue Version steht unter diesem alten Namen auf Lances Website).

Andy Drucker
quelle
10
Die Traktabilität von TFNP wäre deutlich überraschender als die von PPAD, da erstere die Existenz von Einwegpermutationen ausschließen und P = (NP-Schnittpunkt-coNP) implizieren würden.
Noam
8

(Ich denke, niemand hat diese ältere Frage jemals mit den neueren Ergebnissen beantwortet; hier geht's :)

  • PPEIND
  • PPEIND

PPEIND

Daniel Apon
quelle
2

Während dies sowieso gestoßen worden ist, kann ich vielleicht die Hybris haben, um eine Heuristik zu erwähnen, die mir in den Sinn kommt.

Ein NP-vollständiges Problem liegt vor, wenn eine Schaltung vorliegt. Gibt es einen Eingang, der als wahr ausgewertet wird?

  • Dieses Problem wäre eindeutig einfach, wenn die Eingabe "explizit" als Liste von Eingabe-Ausgabe-Paaren und nicht "prägnant" als Schaltung dargestellt würde.

  • Das Problem ist eindeutig informationstheoretisch schwierig, wenn es sich bei der Eingabe nicht um eine Schaltung, sondern um eine Black-Box-Oracle-Funktion handelt (alle Eingaben müssen getestet werden).

  • Das Problem bei der Trennung von P und NP besteht darin, zu zeigen, dass Programme Schaltkreise nicht effizient zerlegen können.

PPAD-vollständige Probleme weisen hier einige interessante Merkmale auf. Wenn Sie an End-of-the-Line denken, wird "ein prägnant dargestelltes Diagramm mit einigen Einschränkungen angegeben, und eine Quelle findet eine Senke". Und ich denke, es teilt die obigen drei Punkte.

usul
quelle
-1

Dieses Papier ist insofern relevant, als es zu zeigen versucht, dass PPAD = P: https://arxiv.org/abs/1609.08934

Samuel Schlesinger
quelle
7
Es gibt unzählige Arbeiten mit P = NP. Ich würde es nicht für relevant halten, bis es ordnungsgemäß begutachtet und veröffentlicht wird.
Emil Jeřábek unterstützt Monica am
Der erste Fehler ist die letzte Zeile des Beweises von Lemma 10 auf Seite 18, da "f (alpha, eps) <0 für eps = 0 und lim_alpha f (alpha, eps) = unendlich für eps> 0" nicht unmöglich ist. auch wenn f (alpha, epsilon) eine stetige Funktion aus alpha und epsilon ist. Da das Papier jedoch einen expliziten Algorithmus enthält, möchten Sie sicherlich auch ein explizites Gegenbeispiel, bei dem dieser Algorithmus fehlschlägt, bevor Sie behaupten können, dass Sie das Papier widerlegt haben.
Thomas Klimpel