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?
(Ich denke, niemand hat diese ältere Frage jemals mit den neueren Ergebnissen beantwortet; hier geht's :)
quelle
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.
quelle
Dieses Papier ist insofern relevant, als es zu zeigen versucht, dass PPAD = P: https://arxiv.org/abs/1609.08934
quelle