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

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 )$n$$O(n^{2-o(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?

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 :))$\alpha(n)$

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.

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.)

• $\Omega(n)$$\Omega(\log n)$

  $O(1)$

• $\Omega(n \log n)$$O(n)$

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

$k$$k$$k$

$k$$P=NP$$k$$\Omega(n^k) )$

$k$

$\tilde{O}(n^6)$$\tilde{O}(n^3)$

$O(n^{2-\epsilon})$

$\sf{P}$$\Omega(n^{1-\epsilon})$

$O(n^2/\log n)$