Gibt es NP-vollständige Probleme mit polynomisch erwarteten Zeitlösungen?

24

Gibt es NP-vollständige Probleme, für die ein Algorithmus bekannt ist, bei dem die erwartete Laufzeit polynomiell ist (für eine sinnvolle Verteilung auf die Instanzen)?

Wenn nicht, gibt es Probleme, für die die Existenz eines solchen Algorithmus nachgewiesen wurde?

Oder impliziert die Existenz eines solchen Algorithmus die Existenz eines deterministischen polynomiellen Zeitalgorithmus?

cc.complexity-theory np-hardness Steve Kroon
quelle

6

Ich verstehe die Frage nicht ganz. Fragen Sie nach Durchschnittsergebnissen für NP-harte Probleme oder fragen Sie, ob wir NP-harte Probleme im schlimmsten Fall in der erwarteten Polynomzeit lösen können?

Moritz

2

Was meinst du mit "voraussichtliche Laufzeit"? Erwarten Sie eine zufällige Verteilung der Eingaben (wie die meisten Antworten zu vermuten scheinen) oder eine Verteilung der vom Algorithmus verwendeten zufälligen Bits (die übliche Bedeutung für zufällige Algorithmen) oder beides?

Jeffs

@Moritz: Ich frage nach durchschnittlichen Ergebnissen für NP-harte Probleme. Das Lösen von NP-harten Problemen im schlimmsten Fall in der erwarteten Polynomzeit scheint mir ein noch stärkeres Ergebnis zu sein, daher würde ich mich auch für solche Ergebnisse interessieren. @JeffE Ich spreche von der erwarteten Zeit für eine Verteilung über die Instanzen. Wenn der Algorithmus zufällig ist, würde man die Erwartung auch über die zufälligen Bits nehmen. Meine Frage bezieht sich jedoch nicht primär auf randomisierte Algorithmen.

Steve Kroon

3

Mit einer einfachen Polstertechnik können Sie diese aus jedem Problem konstruieren.

Angenommen, ist eine vollständige Sprache, für deren Lösung wird. Dann ließ sein Dann wird wie folgt gelöst: Eine lineare Zeit Algorithmus prüft , ob eine Eingabezeichenfolge hat eine gerade Anzahl von Zeichen , von denen die ersten sind . Wenn nicht, lehnt es ab; sonst löst es . Wenn gleichmäßig zufällig gezogen wird, die erwartete Zeit zu lösen ist $L$ $NP$ $O(2^{n})$ $K$

K = {1^{n} x | ‖ x ‖ = n and x \in L}

$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$

K

$K$

n

$n$

1^{n}

$1^n$

x \overset{?}{\in} L

$x\overset{?}{\in}L$

y \in_{R} {0, 1}^{2 n}

$y\in_R \{0,1\}^{2n}$

y \overset{?}{\in} K

$y\overset{?}{\in}K$

\frac{1}{2^{2 n}} (2^{n} \cdot 2^{n} + (2^{2 n} - 2^{n}) O (n)) = 1 + (1 - \frac{1}{2^{n}}) O (n) \in O (n) .

$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$

$K$ ist vollständig. Eine Reduktion von ist: $NP$ $L$

x \in {0, 1}^{n} \mapsto 1^{n} x

$x\in \{0,1\}^n \mapsto 1^nx$

Lieuwe Vinkhuijzen
quelle

13

Es gibt einen polynomialen Zeitalgorithmus zum Auffinden von Hamilton-Zyklen in Zufallsgraphen, der asymptotisch mit der gleichen Wahrscheinlichkeit erfolgreich ist, dass ein Hamilton-Zyklus existiert. Natürlich ist dieses Problem im schlimmsten Fall NP-hart.

Sie zeigen auch, dass ein dynamischer Programmieralgorithmus, der garantiert immer einen Hamilton-Zyklus findet, wenn er existiert, eine polynomiell erwartete Laufzeit hat, wenn die Eingangsverteilung gleichmäßig zufällig über die Menge aller Vertex-Graphen ist. $n$

Referenz: "Ein Algorithmus zum Finden von Hamilton-Zyklen in Zufallsgraphen"

Bollobas, Fenner, Fries

http://portal.acm.org/citation.cfm?id=22145.22193

Aaron Roth
quelle

10

Zu Ihrer letzten Frage, ob die Existenz eines guten Durchschnittsalgorithmus die Existenz eines guten Worst-Case-Algorithmus implizieren würde: Dies ist eine wichtige offene Frage, die besonders für Kryptografen von Interesse ist. Die Kryptographie erfordert im Durchschnitt schwierige Probleme, aber Kryptographen möchten ihre Konstruktionen auf die minimal möglichen Annahmen stützen. Daher ist es von großem Interesse, Probleme zu finden, bei denen die durchschnittliche Fallhärte nachweislich der schlechtesten Fallhärte entspricht.

Es ist bekannt, dass mehrere Gitterprobleme solche Verringerungen im schlimmsten bis mittleren Fall aufweisen. Siehe z. B. Generieren von harten Instanzen von Gitterproblemen von Ajtai und einen Umfrageartikel von Micciancio.

Ian
quelle

9

Grundsätzlich kann der maximale 2-CSP für Variablen und zufällig ausgewählte Nebenbedingungen in der erwarteten linearen Zeit gelöst werden (die genaue Formulierung des Ergebnisses finden Sie in der nachstehenden Referenz). Beachten Sie, dass Max 2-CSP NP-hart bleibt, wenn die Anzahl der Klauseln der Anzahl der Variablen entspricht, da es NP-hart ist, wenn das Beschränkungsdiagramm der Instanz einen Maximalgrad von höchstens 3 aufweist und Sie einige Dummy-Variablen hinzufügen können, um den Durchschnitt zu verringern grad auf 2. $n$ $n$

Referenz:

Alexander D. Scott und Gregory B. Sorkin. Lösen spärlicher zufälliger Instanzen von Max Cut und Max 2-CSP in linearer erwarteter Zeit. Kamm. Probab. Comput., 15 (1-2): 281-315, 2006. Preprint

Serge Gaspers
quelle

2

Ich verstehe nicht, wie Ihre Aussage mit den Angaben in der Zeitung übereinstimmt. In der Arbeit wird über die Lösung von Max 2-CSP gesprochen, wenn der zugrunde liegende Graph ein Zufallsgraph im G (n, c / n) -Modell für ein festes c ist. Dies bedeutet, dass es sich um einen Graphen auf n Eckpunkten handelt, bei dem jede Kante mit der Wahrscheinlichkeit c unabhängig auftritt / n, daher gibt es erwartungsgemäß -Kanten (Bedingungen) in der Instanz. Wenn Sie jedoch die NP-Härte reduzieren, um harte Instanzen mit n Ecken und n Kanten zu erhalten, folgt die Verteilung der Instanzen NICHT dem -Modell, und daher würde ich nicht sagen, dass das Papier eine NP-Härte löst Problem.

Θ (n)

$\Theta(n)$

G (n, c / n)

$G(n,c/n)$

Bart Jansen

@Bart: Ich hätte die Frage vielleicht falsch verstanden. Ich behaupte, dass Max 2-CSP mit einer linearen Anzahl von Klauseln NP-hart ist, aber dass es einen Algorithmus mit erwarteter linearer Zeit gibt, der dieses Problem für zufällige Instanzen löst.

Serge Gaspers

Grundsätzlich, wenn ich Ihr Argument richtig verstehe, sagen Sie, dass Max 2-CSP, das mit der Verteilung G (n, c / n) über die zugrunde liegenden Graphen ausgestattet ist, in der erwarteten linearen Zeit gelöst werden kann. Ich stimme Bart darin zu, dass die Verteilung für mich nicht ganz "sinnvoll" oder "natürlich" erscheint, aber ich denke, dass sie meine Frage angemessen beantwortet.

Steve Kroon

@Steve: Ich stimme zu.

Serge Gaspers

7

Dies beantwortet Ihre Frage nicht vollständig, aber für eine Übersicht der Ergebnisse bei zufälligen 3-SAT-Instanzen sehen Sie Folgendes: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Normalerweise ist es schwierig zu definieren, was "sinnvolle Verteilung" wirklich bedeutet. Sie können diesem Link folgen, um mehr darüber in der Umfrage "Average-Time Complexity" von Bogdanov und Trevisan zu erfahren: http://arxiv.org/abs/cs/0606037 .

Grigory Yaroslavtsev
quelle

Danke für die Links. Leider sind die Ergebnisse des 3-SAT-Papiers "mit hoher Wahrscheinlichkeit" (soweit ich sehen kann) nicht stark genug, um meine Anfrage zu bestätigen. Ich bin damit einverstanden, dass "vernünftige Verteilung" haarig sein kann. In diesem Fall würde ich es vorziehen, wenn die Verteilung nicht offensichtlich gewählt wird, damit der "effektive Instanzraum" das Problem nicht einfach auf einen reduziert, von dem bekannt ist, dass er in P.

Steve Kroon

5

"Färben von Zufallsgraphen in erwarteter Polynomialzeit" von Amin Coja-Oghlan und Anusch Taraz

$G \in G(n, p)$ $p < 1.01/n$ $O(√np)$

http://www.springerlink.com/content/87c17d4dacbrc0ma/

Joel Rybicki
quelle

Gibt es NP-vollständige Probleme mit polynomisch erwarteten Zeitlösungen?

Antworten: