Bei welchen Problemen in P ist es einfacher, das Ergebnis zu überprüfen, als es zu finden?

52

Für ( Suchversionen ) von NP- vollständigen Problemen ist die Überprüfung einer Lösung eindeutig einfacher als das Auffinden, da die Überprüfung in Polynomzeit erfolgen kann, während das Auffinden eines Zeugen (wahrscheinlich) exponentielle Zeit in Anspruch nimmt.

In P kann die Lösung jedoch auch in Polynomzeit gefunden werden, so dass es nicht offensichtlich erscheint, wann die Verifikation schneller ist als das Finden der Lösung. Tatsächlich scheinen sich verschiedene Probleme aus dieser Sicht unterschiedlich zu verhalten. Einige Beispiele:

  1. 3SUM: Bei Eingangszahlen finden Sie 3 davon, die sich zu 0 summieren. Soweit ich weiß, läuft der schnellste bekannte Algorithmus in der Zeit , und diese Reihenfolge wird als optimal angenommen. Andererseits ist die Überprüfung einer Lösung viel schneller, da wir nur überprüfen müssen, ob die 3 gefundenen Zahlen tatsächlich 0 ergeben.O ( n 2 - o ( 1 ) )nO(n2o(1))

  2. All-Pairs Shortest Paths: Berechnen Sie bei einem Diagramm mit Kantengewichten die Matrix für den kürzesten Pfadabstand. Kann nach der Angabe einer solchen Matrix schneller überprüft werden, ob es sich tatsächlich um die richtige Distanzmatrix handelt, als sie neu zu berechnen? Meine Vermutung ist, dass die Antwort vielleicht ja ist, aber es ist sicherlich weniger offensichtlich als für 3SUM.

  3. Lineares Programmieren. Wenn eine behauptete optimale Lösung angegeben wird, ist die Überprüfung einfacher als die erneute Berechnung, wenn auch zusätzliche Informationen angegeben werden (eine optimale duale Lösung). Wenn andererseits nur die ursprüngliche Lösung verfügbar ist, ist nicht klar, ob man sie schneller überprüfen kann, als die LP tatsächlich zu lösen.

Frage: Was ist zu diesem Thema bekannt? Das heißt, wann ist es einfacher, eine Lösung für ein Problem in P zu überprüfen , als die Lösung zu finden?

Andras Farago
quelle
7
Ich denke, dass viele Beispiele von NP-vollständigen Problemen stammen, die in P fallen, wenn wir einige Parameter korrigieren. Überprüfen Sie beispielsweise, ob ein Diagramm eine Clique der Größe für festes k enthält . Die Überprüfung dauert linear, aber wenn P = NP ist, hängt die Komplexität des Suchproblems (Polynom) von kkkk
Marzio De Biasi
16
Wir können überprüfen, ob eine Liste mit ganzen Zahlen mit n - 1 Vergleichen sortiert ist , aber es sind Θ ( n log n ) Vergleiche erforderlich, um eine nicht sortierte Liste zu sortieren. nn1Θ(nlogn)
Thomas
7
Soll es einfach sein, sowohl Ja- als auch Nein-Instanzen auf Entscheidungsprobleme zu überprüfen? Für 3SUM ist es zwar einfach, Ja-Instanzen in konstanter Zeit zu überprüfen, ich weiß jedoch nicht, ob es einfach ist, eine Nein-Instanz zu überprüfen. Oder denken Sie eher an Probleme, bei denen es eine nicht-boolesche Ausgabe gibt, wie z. B. eine Matrixmultiplikation? (Die Matrixmultiplikation ist ein Beispiel dafür, was Sie möchten, wenn Sie randomisierte Algorithmen zulassen.)
Robin Kothari,
3
"Andererseits ist die Überprüfung einer Lösung viel schneller, da wir nur überprüfen müssen, ob die 3 gefundenen Zahlen tatsächlich 0 ergeben." - Wir müssen auch überprüfen, ob die 3 gefundenen Zahlen tatsächlich Teil der Eingabe sind.
HDV
3
Gibt es Probleme, bei denen wir wissen, dass die Überprüfung nicht einfacher ist?
Raphael

Antworten:

24

Es ist bekannt, dass mit einem Graphen G und einem Baum T in linearer Zeit überprüft werden kann, dass T ein minimaler Spannbaum von G ist. Wir haben jedoch noch keinen deterministischen linearen Zeitalgorithmus zur Berechnung der MST. Natürlich ist die Lücke klein (1 vs ), aber es ist immer noch da :))α(n)

Suresh Venkat
quelle
4
Vielleicht kann man hinzufügen, dass es einen randomisierten Algorithmus gibt, der in der erwarteten linearen Zeit abläuft (der Karger-Klein-Tarjan-Algorithmus).
Sasho Nikolov
2
Falls jemand einen Link haben möchte, ist dies der einfachste mir bekannte lineare MST-Überprüfungsalgorithmus: webhome.cs.uvic.ca/~val/Publications/Algorithmica-MSTverif.ps .
Sasho Nikolov
20

Dieses Papier zeigt , dass es Verifikationsalgorithmen für beide YES und NO - Instanzen für 3 Probleme, einschließlich Max Flow, 3sum und APSP, die durch ein schneller sind Polynomfaktor als die bekannten Grenzen für die Berechnung der Lösung selbst.

Es gibt eine Klasse von Problemen, nämlich diejenigen, bei denen die Verbesserung der Laufzeit SETH-schwer ist, wobei die Laufzeit zur Überprüfung von NO-Instanzen wahrscheinlich nicht wesentlich schneller ist als die Zeit zur Berechnung der Lösung, andernfalls lautet die Vermutung aus dieser Veröffentlichung nicht deterministisch Eine starke exponentielle Zeithypothese würde scheitern.

Thatchaphol
quelle
18

Bei einigen Problemen scheint es keinen Unterschied zu geben. Insbesondere zeigen Vassilevska Williams & Williams :

  • Für die boolesche Matrixmultiplikation wird das Matrixprodukt berechnet und das subkubische Äquivalent des Matrixprodukts überprüft. Dies bedeutet, dass beide entweder über subkubische Zeitalgorithmen verfügen oder keiner von beiden.

  • Das Gleiche gilt für die Berechnung und Überprüfung von Matrixprodukten über jede "erweiterte (min, +) Struktur" (siehe Papier für die Definition, aber dies beinhaltet viele natürliche Probleme).

(Nun ist es natürlich möglich, dass diese Probleme alle subkubische Algorithmen haben, und dann könnte es einen polynomiellen Unterschied zwischen Rechnen und Verifizieren geben, aber für diese Probleme kann es keinen kubischen Unterschied geben. Und das erscheint mir plausibel Tatsache, dass sie alle im Wesentlichen kubische Zeit benötigen.)

Joshua Grochow
quelle
2
Andererseits gibt es für die Matrixmultiplikation in einem ausreichend großen Feld einen quadratischen, zeitlich zufälligen Algorithmus zur Verifikation, während die schnellste Laufzeit für die Berechnung des Produkts nΩ beträgt.
Thatchaphol
2
@Thatchaphol: Ja, obwohl viele Leute Omega = 2 glauben ... Es ist auch allgemein anerkannt, dass die Boolesche Matrixmultiplikation (dh die Berechnung von Matrixmultiplikationen über den Booleschen Wert und / oder den Halbring) eine etwas andere Natur hat als die Matrixmultiplikation über a Feld.
Joshua Grochow
16
  • Ω(n)Ω(Logn)

    O(1)

  • Ω(nLogn)O(n)

Raphael
quelle
2
Ω(nLogn)O(1)
O(n)
Θ(n)
10

Ich denke, dass viele Beispiele von NP-vollständigen Problemen stammen, die in P fallen, wenn wir einen oder mehrere Parameter korrigieren .

kkk

kP=NPkΩ(nk))

k

Marzio De Biasi
quelle
9

O~(n6)O~(n3)

Joe Bebel
quelle
das komplement (die zusammensetzung) ist noch leichter zu beobachten!
Yonatan N
3

O(n2-ϵ)

PΩ(n1-ϵ)

O(n2/Logn)

SamM
quelle