Probleme, die verwendet werden können, um Ergebnisse der Polynomzeithärte anzuzeigen

58

Wenn ich einen Algorithmus für ein neues Problem entwerfe und nach einiger Zeit keinen Polynom-Zeit-Algorithmus mehr finde, kann ich versuchen, zu beweisen, dass er NP-schwer ist. Wenn es mir gelingt, habe ich erklärt, warum ich den Polynom-Zeit-Algorithmus nicht gefunden habe. Es ist nicht so, dass ich mit Sicherheit weiß, dass P! = NP ist, es ist nur so, dass dies das Beste ist, was mit dem aktuellen Wissen erreicht werden kann, und in der Tat ist der Konsens, dass P! = NP ist.

Angenommen, ich habe für ein Problem eine Lösung für die Polynomzeit gefunden, aber die Laufzeit ist . Nach viel Mühe mache ich keine Fortschritte bei der Verbesserung. Also könnte ich stattdessen versuchen zu beweisen, dass es 3SUM-schwer ist. Dies ist in der Regel ein zufriedenstellender Zustand, nicht weil ich der Ansicht bin, dass 3SUM tatsächlich Zeit benötigt, sondern weil dies der aktuelle Stand der Technik ist und viele kluge Köpfe versucht haben, ihn zu verbessern. und sind gescheitert. Es ist also nicht meine Schuld, dass es das Beste ist, was ich tun kann. $O(n^2)$ $\Theta(n^2)$

In solchen Fällen ist das Beste, was wir tun können, ein Härteergebnis anstelle einer tatsächlichen Untergrenze, da wir für Turingmaschinen keine superlinearen Untergrenzen für Probleme in NP haben.

Gibt es eine einheitliche Reihe von Problemen, die für alle Polynomlaufzeiten verwendet werden können? Wenn ich zum Beispiel beweisen möchte, dass es unwahrscheinlich ist, dass ein Problem einen Algorithmus hat, der besser ist als , gibt es ein Problem X, sodass ich zeigen kann, dass es X-schwer ist, und belasse es dabei? $O(n^7)$

Update : Diese Frage wurde ursprünglich für Problemfamilien gestellt. Da es nicht so viele Problemfamilien gibt und diese Frage bereits ausgezeichnete Beispiele für einzelne schwierige Probleme erhalten hat, entspanne ich die Frage zu jedem Problem, das für polynomielle Zeithärteergebnisse verwendet werden kann. Ich füge dieser Frage auch ein Kopfgeld hinzu, um mehr Antworten zu ermutigen.

cc.complexity-theory lower-bounds conditional-results Robin Kothari
quelle

5

Die Seite maven.smith.edu/~orourke/TOPP/P11.html fasst einige Ergebnisse zu unteren (und oberen) Grenzen von 3SUM und verwandten Problemen zusammen und ist lesenswert.

Tsuyoshi Ito

2

P

$P$

Ω (n^{i})

$\Omega(n^i)$

Ω (n^{i + 1})

$\Omega(n^{i+1})$

3

Off Topic: Robin, Tsuyoshi, danke für die Einführung der 3SUM-Familie der unteren Schranken: Ich hatte noch nie davon gehört.

Gphilip

2

@ Tsuyoshi: Danke für die Information. Dies ist eine schöne Umfrage zum Thema: cs.mcgill.ca/~jking/papers/3sumhard.pdf . @gphilip: Ich wurde kürzlich von einigen rechnergestützten Geometern in dieses Problem eingeführt. Ich denke, es ist in diesem Bereich sehr bekannt.

Robin Kothari

Gute Frage. Können Sie klarstellen, was Sie unter "Uniform" verstehen: Möchten Sie den Umfang der Vorverarbeitung des Parameters begrenzen?

András Salamon,

35

$k$ $O(n^{\lceil k/2 \rceil})$ $n^7$ $n^{6.99}$ $14$

$k$ $k$ $k$ $2k$ $O(n^2)$ $n$ $2k$ $k$ $0$ $O(n^{k/2-\varepsilon})$ $k$ $O(n^{k-2\varepsilon})$ $2k$ $2k$ $k$

$k$ $O(\log n)$ $O(n^2)$ $3$ $k$ $W\[1\]$ $k$ $W\[2\]$

$3$ $TIME[n^2]$ $TIME[n^2]$ $3$ $3$ $O(\log n)$ $3$ $P \neq NP$ $n^2$ $n^2$

Ryan Williams
quelle

4

O (n^{2} .376)

$O(n^2.376)$

Θ (n^{k})

$\Theta(n^k)$

k

$k$

k

$k$

k

$k$

O (n^{k / 2})

$O(n^{k/2})$

k

$k$

k

$k$

O (n^{k / 2})

$O(n^{k/2})$

n^{2}

$n^2$

@ Ryan: Du hast recht, sie sind die gleichen. Obwohl wir mit k-SUM zumindest in schwächeren Modellen Beweise dafür haben, dass die vermutete Grenze korrekt ist. Ich kenne keine Argumente, die nahelegen, dass eine 3-Clique nicht schneller lösbar sein sollte als eine Matrixmultiplikation.

Robin Kothari

n^{f (k)}

$n^{f(k)}$

f (k) = Θ (k)

$f(k) = \Theta(k)$

14

$\Omega^\star(n^3)$

Mihai
quelle

2

Wie wäre es mit dem Durchmesser eines Graphen? Besser noch, machen Sie daraus ein Entscheidungsproblem "Ist der Durchmesser mindestens k?". Dies hat den Vorteil, dass meines Wissens keine offensichtliche superlineare Bindung besteht.

Raphael

9

$d$ $O(n^d)$ $n$ $d$ $d+1$

$(d+1)$ $k$ $\Omega(n^{\lfloor d/2 \rfloor +1})$ $d \geq 3$

J. Erickson, S. Har-Peled und DM Mount, On the Least Median Square Problem, Diskrete und rechnergestützte Geometrie, 36, 593-607, 2006. http://www.cs.umd.edu/~mount/Papers /dcg06-lms.pdf

J. Erickson und R. Seidel. Bessere Untergrenzen beim Erkennen einer Neigung und sphärischer Entartungen. Discrete Comput. Geom., 13: 41–57, 1995. http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html

J. Erickson. Neue untere Schranken für konvexe Rumpfprobleme in ungeraden Dimensionen. SIAM J. Comput., 28: 1198–1214, 1999. http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html

Guilherme D. da Fonseca
quelle

Diese Antwort gefällt mir, aber können Sie sie erläutern? Warum wird es geglaubt?

Aaron Sterling

8

$\Theta(n^{4/3})$ $n$ $n$

Jeffε
quelle

7

Gibt es nicht-geometrische Probleme, die sich auf Hopcrofts Problem reduzieren?

Suresh Venkat

Ich habe beschlossen, die Prämie für diese Antwort zu vergeben, weil ich noch nie von diesem Problem gehört hatte.

Robin Kothari

Probleme, die verwendet werden können, um Ergebnisse der Polynomzeithärte anzuzeigen

Antworten: