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

23

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 xf(x)xf(x)nx

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 mg

maxxf(x)=minyg(y)
xnymnm

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!

Andras Farago
quelle

Antworten:

22

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 ( yP=NPcoNPLNPcoNPFGxLy:F(x,y)xLy:G(x,y)fx(y)=1F(x,y)g x ( yfx(y)=0gx(y)=0G(x,y)gx(y)=1maxyfx(y)=minygx(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).NPcoNPPi

Noam
quelle
9
Ich habe den Eindruck , dass manche Menschen sogar so weit gehen zu nehmen als Definition der „gute Charakterisierung“. NPcoNP
Joshua Grochow
Eine Liste solcher Probleme finden Sie unter mathoverflow.net/questions/31821/…
Rahul Savani,
14

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:GGGTxTS(x)G

  1. Für alle , | S ( x ) | k + 1 .xV(T)|S(x)|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.uV(G)TxuS(x)
  4. Jede Kante ist eine Teilmenge von etwas S ( x ) für x V ( T ) .(u,v)E(G)S(x)xV(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:GkG

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

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 2kkkk1/2+ϵ der Polynomgröße.k1/2/O(log2k)

Sasho Nikolov
quelle
1
Vielen Dank, es ist ein sehr schönes Beispiel, auch wenn es nicht in die Kategorie fällt, die ich suche. Es ist interessant festzustellen, dass dieses Min-Max-Theorem über die Baumbreite 1993 veröffentlicht wurde und zu diesem Zeitpunkt die NP-Vollständigkeit der Baumbreite bereits bekannt war. Daher könnte das Ergebnis als Grund für die Vermutung von NP = coNP gedient haben. Während die exponentielle Untergrenze der Brombeerstrauchgröße sie für diese Rolle endgültig disqualifizierte, wurde diese Untergrenze erst 16 Jahre später veröffentlicht.
Andras Farago
Andras, zu der Zeit war es auch bekannt, dass das Schlagen von Sets im Allgemeinen NP-schwer ist (es war eines der 21 Probleme von Karp). Selbst bei Brombeersträuchern mit polynomischer Größe ist die Berechnung der Reihenfolge nicht einfach, es sei denn, Sie können die Struktur von Brombeersträuchern irgendwie verwenden. Trotzdem ist es interessant, dass die Größe von Brombeeren nicht früher untersucht wurde.
Sasho Nikolov
13

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(nn)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

Rahul Savani
quelle