Härtesprünge in der rechnerischen Komplexität?

Das Problem der minimalen Bandbreite besteht darin, eine Reihenfolge von Graphknoten auf einer ganzzahligen Linie zu finden, die den größten Abstand zwischen zwei benachbarten Knoten minimiert. Eine Raupe ist ein Baum, der aus einem Hauptpfad gebildet wird, indem -lange, kantendisjunkte Pfade höchstens von ihren Knoten entfernt wachsen ( wird als Haarlänge bezeichnet). Das Problem der minimalen Bandbreite ist in für 2-Raupen, aber es ist vollständig für 3-Raupen.k k P N $k$$k$$k$$P$$NP$

Hier ist eine sehr interessante Tatsache: Das Problem der minimalen Bandbreite ist in Polynomzeit für 1-Raupen (Haarlänge höchstens 1) lösbar, für zyklische 1-Raupen ist es jedoch vollständig (bei zyklischen Raupen wird eine Kante hinzugefügt, um die Endpunkte zu verbinden des Hauptweges). Das Hinzufügen von genau einer Kante macht das Problem vollständig.N $NP$$NP$

Was ist das auffälligste Beispiel für einen Problemhärtesprung, bei dem eine kleine Variation der Eingabeinstanz einen Komplexitätssprung von der Polynomzeitlösbarkeit zur Vollständigkeit verursacht?$NP$

Eines der interessanteren angewandten Beispiele für Härtesprünge ist in folgendem Problem zu beobachten:

Stellen Sie sich eine Fußball-Meisterschaft mit Mannschaften vor: Das Problem, zu entscheiden, ob eine bestimmte Mannschaft die Liga (noch) gewinnen kann, ist P, wenn in einem Spiel die siegreiche Mannschaft 2 Punkte erhält, die eine 0 verliert und jede Mannschaft 1 Punkte erhält Punkt in einem Unentschieden. Aber wenn wir die Regeln so ändern, dass das Gewinnerteam 3 Punkte erhält, wird das gleiche Problem zu N P -hart.$n$$P$$NP$

Das Ergebnis kann für jede -Punktregel für jedes k > 2 und sogar für nur drei verbleibende Runden verallgemeinert werden .$(0, 1, k)$$k > 2$

Quelle: „Komplexitätstheorie“ von Ingo Wegener ( http://portal.acm.org/citation.cfm?id=1076319 )

Dies beantwortet die im Fragentitel gestellte Frage, aber nicht die in der Frage gestellte.

Ein schockierendes Beispiel für Einsprunghärte ergibt sich aus der Frage: "Wie viele befriedigende Aufgaben hat eine planare Formel, Modulo ?" Es wurde allgemein angenommen, dass dies # P-schwer ist, und es ist für "die meisten" Werte von n , aber wenn n eine Mersenne-Ganzzahl ist (zum Beispiel n = 7 , weil 7 die Form 2 3 - 1 hat ), dann ist die Antwort kann in polynomialer Zeit berechnet werden.$n$$n$$n$$n=7$$2^3-1$

Dies wurde erstmals von Valiant in seiner bahnbrechenden Arbeit über holographische Algorithmen entdeckt.

INDEPENDENT SET ist NP-vollständig für (Kreuz-, Dreieck-) freie Graphen , kann jedoch für (Stuhl-, Dreieck-) freie Graphen in linearer Zeit gelöst werden . (Die X-freien Graphen sind solche, die keinen Graphen von X als induzierten Subgraphen enthalten.)

Stuhl: Dreieck: Kreuz:

Beachten Sie, dass das Kreuz vom Stuhl durch Hinzufügen einer einzelnen Kante erhalten wird.

Ich bin mir nicht sicher, ob ich Ihrer Charakterisierung zustimmen würde, dass das Hinzufügen einer einzelnen Kante zur Eingabe das Problem NP-vollständig macht, da man tatsächlich zulässt, dass zu jeder der unendlich vielen Eingabeinstanzen eine Kante hinzugefügt wird.

Hier ist ein Beispiel für ein Problem, das eine scharfe Zweiteilung in der von Ihnen vorgeschlagenen Richtung aufweist.

Das Problem der Bestimmung, ob es einen Graphhomomorphismus von dem Eingabegraph G zu einem festen Schablonendiagramm H gibt, liegt in P, wenn H ein Graph mit einer Selbstschleife oder ein zweigliedriger schleifenloser Graph ist. Wenn H nicht zweiteilig ist (dies kann oft durch Hinzufügen einer einzelnen Kante erreicht werden), ist das Problem NP-vollständig.

• P. Hell und J. Nešetřil, Komplexität der H-Färbung , J. Comb. Th. B 48 92-110, 1990. doi: 10.1016 / 0095-8956 (90) 90132-J

Der Schlüssel hier ist, dass die 2-Färbung in P ist (dies entspricht einem Homomorphismus zu , dem Pfad auf 3 Eckpunkten), während die 3-Färbung NP-vollständig ist (dies entspricht einem Homomorphismus zu K 3 , dem Dreieck).$P_3$$K_3$

Hier ist ein weiteres interessantes Beispiel für die Erkennung induzierter Subgraphen:

Ein Theta ist ein Graph mit nicht benachbarten Eckpunkten $x,y$ , drei Pfaden $P_1, P_2, P_3$ von $x$ nach $y$ , wobei zwei beliebige Pfade einen Zyklus mit einer Länge von mehr als 3 induzierten.

Eine Pyramide ist ein Graph mit einem Scheitelpunkt $x$ , einem Dreieck $y_1,y_2,y_3$ und Pfaden $P_i$ von $x$ bis $y_i$ für jedes $i=1,2,3$ mit höchstens einem Pfad mit der Länge eins.

Schließlich ist ein Prisma ein Graph mit zwei Dreiecken $x_1,x_2,x_3$ und $y_1,y_2,y_3$ und Pfaden $P_i$ von $x_i$ bis $y_i$ für jedes $i=1,2,3$ .

In Zahlen lässt sich leicht beschreiben:

Für die Detektion von induziertem Theta und Pyramide ist es bekannt, dass es sich in Polynomzeit befindet. (Tatsächlich benötigt der bekannteste Algorithmus für Theta die Zeit $O(n^{11})$ und für die Pyramide die Zeit $O(n^9)$ .) Für die Erkennung eines induzierten Prismas wird das Problem jedoch NP-schwer.

Man kann " Detecting Induced Subgraphs " von Leveque, Lin, Maffray und Trotignon als Referenz sehen. Der Grund, warum Theta und Pyramide relativ einfach sind, hängt mit dem "Drei-in-einem-Baum" -Problem zusammen, das in " Das Drei-in-einem-Baum-Problem " von Chudnovsky und Seymour beschrieben wird.

ähm ... ich bin sicher, Sie suchen nach weniger trivialen Beispielen ... aber ich möchte darauf hinweisen, dass die Zahl gegen 3 etwas Besonderes ist . 2 - S A T bis 3 - S A T , 2 - C O L vs 3 - C O L usw. Intuitiv habe ich immer gedacht, dass ein Knoten mit höchstens 2 Kanten höchstens eine Linie bilden kann. aber ein Knoten mit 3 Kanten kann einen Baum bilden, wenn wir uns von 2-3 bewegen, erhalten wir eine kombinatorische Explosion.$2$$3$$2-SAT$$3-SAT$$2-COL$$3-COL$

Ich denke, dass es nicht sinnvoll ist, über Instanzen zu sprechen. Wir können über zwei Verteilungen von Eingabeinstanzen mit unterschiedlichen Schwierigkeiten sprechen, aber es wäre interessanter, wenn es eine Beziehung zwischen der Verteilung oder zwischen Instanzen in den Verteilungen gibt.

Wir können eine parametrisierte Familie von Verteilungen betrachten und dann darüber sprechen, was passiert, wenn wir den Parameter ändern. Sie interessieren sich vielleicht für das sogenannte Schwellenwertphänomen , "bei dem ein System aufgrund einer geringfügigen Änderung eines Parameters eine schnelle qualitative Änderung erfährt ...". Schauen Sie sich diese Umfrage an: Ehud Friedgut , " Hunting for Sharp Thresholds ", Random Structures Algorithms 26, 2005.

Ich denke, eines der auffälligsten und schönsten Beispiele ist das zufällige k-SAT mit der Klauseldichte , der Phasenübergang ist wirklich erstaunlich.$\Delta$

Folgern Typen für Lambda - Ausdrücke ist DEXPTIME-komplett mit pränexe und Rang-2 polymorphen Systemen des Typs (bei Typ quantifiers höchstens eine Ebene tief verschachtelt ist), wird aber unentscheidbar für Rang-3 und höher. Seltsamerweise kann eine zusätzliche Verschachtelungsebene ein Problem unentscheidbar machen.

Finden des Grundzustands eines planaren Ising-Modells mit 0 Magnetfeldern ist in P, mit einem Magnetfeld ungleich Null ist es NP-hart. Die Teilungsfunktion des planaren Ising-Modells mit dem Magnetfeld 0 ist in P, mit dem Magnetfeld ungleich Null ist es NP-hart.

Hier ist ein nettes Problem mit einem interessanten Komplexitätssprung wie der minimalen Bandbreite, die Sie in Ihrer Frage angesprochen haben.

Lassen Sie ein Graph und seine T einen Spannbaum von G . Der Umweg für eine Kante u v ∈ E ( G ) ist der einzigartige u - v Pfad in T . Die Überlastung von e ∈ E ( T ) , bezeichnet durch C n g G , T ( e ) ist die Anzahl von Umleitungen , die enthalten , e . Die Überlastung von G in T , bezeichnet mit c n g$G$$T$$G$$uv\in E(G)$$u$$v$$T$$e \in E(T)$$\mathrm{cng}_{G,T}(e)$$e$$G$$T$ , ist die maximale Überlastung über alle Kanten in T . Der SpanningTreeStaus von G , bezeichnet durch s t c ( G ) ist die minimale Staus über alle Spannbäume von G . Das Spanning Tree Congestion-Problem fragt, ob ein gegebener Graph höchstens einige k Spanning Tree-Staus aufweist.$\mathrm{cng}_G(T)$$T$$G$$\mathrm{stc}(G)$$G$$k$

Der folgende Komplexitätssprung ist dargestellt in: Bodlaender et al., Parametrisierte Komplexität des Überlastungsproblems , Algorithmica 64 (2012) 85–111 :

Für jedes feste und d ist das Problem in linearer Zeit für Graphen mit höchstens d Grad lösbar . Wenn wir dagegen nur einen Scheitelpunkt unbegrenzten Grades zulassen , wird das Problem für jedes feste k ≥ 8 sofort N P -vollständig .$k$$d$$d$$\mathsf{NP}$$k\ge 8$

Ich frage mich, warum niemand dies erwähnt hat:

Horn-Sat gegen K-Sat

Ich denke, jeder weiß, was es ist. Wenn nicht:

Horn-Sat soll herausfinden, ob eine Menge von Horn-Klauseln erfüllt werden kann (jede Klausel hat höchstens 1 positives Literal).

K-Sat ermittelt, ob eine Reihe von Klauseln erfüllt werden kann (jede Klausel kann mehr als 1 positive Literale enthalten).

Das Zulassen von mehr als einem positiven Literal in jeder Klausel macht das Problem von P-complete zu NP-complete.

Grafik-Färbung

Wie in einer anderen Antwort erwähnt, ist 2-COL in der Polynomzeit lösbar, während 3-COL NP-vollständig ist. Wenn Sie jedoch die Anzahl der Farben erhöhen, wird das Problem nach einem (unbekannten?) Punkt einfacher!

Wenn wir beispielsweise N Scheitelpunkte und N Farben haben, kann das Problem gelöst werden, indem jedem Scheitelpunkt eine andere Farbe zugewiesen wird.

In ähnlicher Weise: Permanent vs Determinant.

Ich habe gerade einen Artikel gelesen, der sich mit der Hypergraph-Partitionierung befasst . Das Problem ist wie folgt definiert:

Bei zwei gegebenen Parametern und l ist 1 ≤ $k$$l$$1 \leq l < k$$P^l_k$$\mathcal{H} = (V, \mathcal{E})$$t_1, \dots, t_k$$|V| = n = \sum^k_{i=1} t_i$$|\mathcal{E}| = m$$V$$k$$t_1, \dots, t_k$$\mathcal{E}$$l$

Im Allgemeinen ist nachgewiesen, dass:

• $P^1_k$$n,m$$k \geq 2$
• $P^l_k$$2 \leq l < k$

Wenn dies nicht "springen" genug ist, lesen Sie weiter. Für Hypergraphen mit disjunkten Hyperkanten wird Folgendes angezeigt:

• $P^1_k$$k \geq 2$
• $P^l_k$$m$$2 \leq l < k$

Laurent Lyaudet. 2010. NP-harte und lineare Varianten der Hypergraph-Partitionierung. Theor. Comput. Sci. 411, 1 (Januar 2010), 10-21. http://dx.doi.org/10.1016/j.tcs.2009.08.035

Interessante Komplexitätssprünge sind für das Job-Shop-Scheduling-Problem bekannt.

In dem Job-Shop-Problem haben wir eine Menge von Jobs, die auf einer gegebenen Menge M von $n$$M$$m$$j$$\mu_j$$O_{1j},O_{2j},\dots,O_{\mu_jj}$$O_{ij}$$p_{ij}$$m_{ij}\in M$$C_j$$j$

$C_{max}=max_jC_j$$\sum C_j$

$J||\gamma$$\gamma$

$J2|n=k|F$$J|n=2|F$$J2$ $(n=k)$$2$ $(k)$$F$

$J3|n=3|C_{max}$$J3|n=3|\sum C$

$J2||C_{max}$$J2||\sum C$

Somit können wir hier sehen, dass es einen Sprung gibt, wenn wir von zwei Jobs / Maschinen auf drei wechseln.

$\ln n$$(1-o(1))\ln n$

Ich denke, das Pascal-Dreieck wäre es. Jede Zeile im Pascal-Dreieck summiert sich zu $2^n$ . Die Elemente sind Binomialkoeffizienten. Wenn Sie also ein Problem finden, dessen Leistung mit Hilfe von Binomialkoeffizienten beschrieben werden kann, müssen Sie bereits alle Probleme lösen, die mit der n-ten Zeile des Pascal-Dreiecks zusammenhängen$2^n$$(a+b)^n=\sum_{i\in{0..n}}{{n}\choose{i}}a^ib^{n-i}$kann als Polynom (von 'a') dargestellt werden, dessen Faktoren Binomialkoeffizient multipliziert mit Potenzen von 'b' sind. Wenn 'b' konstant ist, ist dies ein Polynom n-ter Ordnung (beschrieben durch zwei Variablen), die wie ein Pascal-Dreieck angeordnet sind. Wenn Sie dann alle Probleme in der n. Reihe lösen, müssen SieDTIME(2n$p_b(a)$$a=b=1$$2^n=p_1(1)$$DTIME(2^n)$$(k<n)$$P=NP=DTIME(2^n)$$P=NP$