Optimierungsprobleme mit guter Charakterisierung, aber ohne Polynom-Zeit-Algorithmus

Betrachten Sie Optimierungsprobleme der folgenden Form. Sei eine polynomiell berechenbare Funktion, die eine Zeichenkette in eine rationale Zahl abbildet . Das Optimierungsproblem lautet: Was ist der Maximalwert von über Bit-Strings ?x f ( x ) n $f(x)$$x$$f(x)$$n$$x$

Nehmen wir an, dass ein solches Problem eine Minimax-Charakterisierung hat , wenn es eine andere berechenbare Polynomzeitfunktion , so dass gilt. Hier läuft über alle n- Bit-Strings, und y läuft über alle m- Bit-Strings. n und m können unterschiedlich sein, sie sind jedoch polynomial verwandt.max x f ( x ) = min y g ( y ) x n y m n $g$

Zahlreiche natürliche und wichtige Optimierungsprobleme weisen eine solche Minimax-Charakterisierung auf. Einige Beispiele (die Theoreme, auf denen die Charakterisierungen basieren, sind in Klammern angegeben):

Lineare Programmierung (LP Duality Thm), Maximaler Durchfluss (Max Flow Min Cut Thm), Max Bipartite Matching (Konig-Hall Thm), Max Nicht-Bipartite Matching (Tutte's Thm, Tutte-Berge-Formel), Max Disjoint Arborescences im gerichteten Graphen ( Edmond's Disjoint Branching Thm), Max Spanning Tree Packing im ungerichteten Graphen (Tutte's Tree Packing Thm), Min. Bedeckung durch Wälder (Nash-Williams Thm), Max. Gerichtete Schnittpackung ( Lucchesi-Younger Thm), Max. 2-Matroid Intersection (Matroid Intersection) Thm), Max disjunkte Pfade (Menger's Thm), Max Antichain in teilweise geordnetem Set (Dilworth Thm) und viele andere.

In all diesen Beispielen ist auch ein Polynom-Zeit-Algorithmus verfügbar, um das Optimum zu finden. Meine Frage:

Gibt es Optimierungsprobleme bei einer Minimax-Charakterisierung, für die bisher kein Polynom-Zeit-Algorithmus gefunden wurde?

Hinweis: Die lineare Programmierung befand sich ungefähr 30 Jahre in diesem Status!

In gewissem technischen Sinne fragen Sie, ob . Nehmen wir an, dass , also die und so dass iff und iff . Dies kann als Minmax-Charakterisierung durch umformuliert werden, wenn und andernfalls; wenn und andernfalls. Nun haben wir tatsächlich .L ∈ N P ∩ C O N P F G x ∈ L ∃ y : F ( x , y ) x ∉ L ∃ y : G ( x , y ) , f x ( y ) = 1 F ( x , y ) f x ( $P = NP \cap coNP$$L \in NP \cap coNP$$F$$G$$x \in L$$\exists y: F(x,y)$$x \not\in L$$\exists y: G(x,y)$$f_x(y) = 1$$F(x,y)$g x ( $f_x(y) = 0$$g_x(y) = 0$$G(x,y)$$g_x(y) = 1$$max_y f_x(y) = min_y g_x(y)$

In diesem Sinne kann jedes Problem, von dem bekannt ist, dass es sich in jedoch nicht bekannt ist, dass es sich in befindet, in eine Antwort auf Ihre Frage umgewandelt werden. ZB Faktorisierung (z. B. die Entscheidungsversion, ob das -te Bit des größten Faktors 1 ist).$NP \cap coNP$$P$$i$

Seymour und Thomas zeigten eine Min-Max-Charakterisierung der Baumbreite. Die Baumbreite ist jedoch NP-hart. Dies ist jedoch nicht ganz die Art von Charakterisierung, nach der Sie fragen, da die Doppelfunktion keine polynomiell zeitberechenbare Funktion eines kurzen Zertifikats ist. Dies ist höchstwahrscheinlich für NP-Gesamtprobleme unvermeidbar, da wir sonst ein NP-Gesamtproblem in coNP hätten, was einen Zusammenbruch von NP = coNP impliziert, und ich würde das als ziemlich schockierend betrachten.$g$

Das Baumweite eines Graphen ist gleich die kleinste Breite einer kleinsten Baumzerlegung von G . Eine Baumzerlegung eines Graphen G ist ein Baum T, so dass jeder Scheitelpunkt x von T durch eine Menge S ( x ) von Scheitelpunkten von G mit der Eigenschaft gekennzeichnet ist:$G$$G$$G$$T$$x$$T$$S(x)$$G$

1. Für alle , | S ( x ) | ≤ k + 1 .$x \in V(T)$$|S(x)| \leq k+1$
2. Die Vereinigung aller ist die Eckenmenge von G .$S(x)$$G$
3. Für jedes ist der Teilgraph von T, der durch alle x induziert wird, für die u ∈ S ( x ) verbunden ist.$u \in V(G)$$T$$x$$u \in S(x)$
4. Jede Kante ist eine Teilmenge von etwas S ( x ) für x ∈ V ( T ) .$(u, v) \in E(G)$$S(x)$$x \in V(T)$

Seymour und Thomas haben gezeigt, dass die Baumbreite gleich der Brombeerstrauchszahl von : das Maximum k, so dass es eine Sammlung zusammenhängender Teilgraphen von G gibt, so dass:$G$$k$$G$

1. Jeweils zwei Teilgraphen kreuzen sich oder sind durch eine Kante verbunden.
2. Kein Satz von Ecken von G trifft auf alle Untergraphen.$k$$G$

Eine solche Sammlung von Untergraphen wird als Brombeerstrauch $k$

Beachten Sie, wie „Brombeerstrauch Nummer mindestens “ ist eine ∃ ∀ Aussage, mit beiden Quantoren über exponentiell große Mengen. Es ist also kein leicht zu überprüfendes Zertifikat (und wenn es eines gäbe, wäre es eine wirklich große Neuigkeit, wie ich oben sagte). Um die Sache noch schlimmer, Grohe und Marx zeigten , dass für jeden k ist eine graphische Darstellung des Baumweite k , so dass jeder Brombeerstrauch Ordnungs mindestens k 1 / 2 + ε von exponentiell viele Subgraphen bestehen muss. Sie zeigen auch , dass es existieren Brombeersträucher der Ordnung k 1 / 2 / O ( log $k$$\exists\forall$$k$$k$$k^{1/2 + \epsilon}$ der Polynomgröße.$k^{1/2}/O(\log^2 k)$

Parity-Spiele, Mean-Payoff-Spiele, Discounted-Spiele und Simple Stochastic-Spiele fallen in diese Kategorie.

Bei allen handelt es sich um unendliche Nullsummenspiele für zwei Spieler, bei denen die Spieler die Eckpunkte kontrollieren und auswählen, wohin ein Token als Nächstes verschoben werden soll. Alle haben Gleichgewichte in memorylosen Positionsstrategien, was bedeutet, dass jeder Spieler deterministisch und unabhängig von der Spielgeschichte einen Rand an jedem Auswahlscheitelpunkt auswählt. Wenn eine Strategie eines Spielers vorausgesetzt wird, kann die beste Antwort des anderen Spielers in Polynomzeit berechnet werden, und die Min-Max-Beziehung, die Sie benötigen, gilt für den "Wert" des Spiels.

Die natürlichen Entscheidungsvarianten dieser Probleme liegen in NP und co-NP (tatsächlich UP und co-UP) und die Funktionsprobleme, um ein Gleichgewicht zu finden, liegen in PLS und PPAD.

Die Algorithmen mit der bekanntesten Laufzeit sind subexponentiell, aber superpolynomiell (z. B. , wobeindie Anzahl der Eckpunkte in der Spielgrafik ist).$O(n^\sqrt{n})$$n$

Siehe zB

David S. Johnson. 2007. Die NP-Vollständigkeitssäule: Nadeln im Heuhaufen finden. ACM Trans. Algorithmen 3, 2, Artikel 24 (Mai 2007). DOI = 10.1145 / 1240233.1240247 http://doi.acm.org/10.1145/1240233.1240247