Natürliche NP-vollständige Probleme mit "großen" Zeugen

28

Die Frage zu cstheory " Was ist NP auf Zeugen linearer Größe beschränkt? " Fragt nach der Klasse NP, die auf Zeugen linearer Größe , aberO(n)

Gibt es natürliche NP-vollständige Probleme, bei denen (ja) Fälle der Größe Zeugen einer Größe größer als erfordern ?nn

Natürlich können wir künstliche Probleme aufbauen wie:

  • L={1nww encodes a satisfiable formula and |w|=n}
  • L={φφ is SAT formula with more than |φ|2 satisfying assignments}

Nach einem kurzen Blick auf G & J scheint jedes natürliche NPC-Problem Zeugen zu haben, die (streng) kleiner als .n

Gibt es einen "Grund / eine Erklärung" dafür?

Marzio De Biasi
quelle
1
Viele Probleme haben die Zeugengröße , wie der Graphisomorphismus und der Hamilton-Pfad. Wollten Sie Polylog-Faktoren ausschließen, oder gilt dies als Antwort? Θ(nlogn)
Joshua Grochow
12
Tatsächlich kann die Zeugengröße für den Graphisomorphismus und den Hamilton-Pfad als sublinear in der Eingabe angesehen werden (vorausgesetzt, die Eingabe ist die Adjazenzmatrix des Graphen). n×n
Ryan Williams
1
Oh, richtig ... oh.
Joshua Grochow
1
@MarzioDeBiasi Ich denke, Ihre Beobachtung kleiner Zeugen sollte verwendet werden, um das natürliche NP-vollständige Problem zu definieren .
Mohammad Al-Turkistany
1
@MarzioDeBiasi - Ich stimme zu, dass eine Liste der zufriedenstellenden Aufgaben ausreicht, aber können Sie nachweisen, dass es keinen kürzeren Zeugen für das Problem gibt? (Vielleicht eine prägnante Darstellung der benötigten Aufgaben).
RB

Antworten:

10

Wie wäre es mit der Kantenfarbzahl in einem dichten Graphen (aka Chromatischer Index )? Sie erhalten die Adjazenzmatrix eines Graphen mit Eckpunkten ( Eingabe von Bit), aber der natürliche Zeuge, der die Färbung beschreibt, hat die Größe . Natürlich kann es kürzere Beweise für Graphen der Klasse 1 im Vizing-Theorem geben .n 2 n 2 log nnn2n2logn

Siehe auch diese möglicherweise verwandte Frage

Andreas Björklund
quelle
2
Es scheint ein gutes Beispiel zu sein! Nur eine Anmerkung: Das Problem ist auch für kubische Graphen NP-vollständig. In diesem Fall haben wir einen Zeugen der Größebits ist genug (zwei Bits für jede Kante), was weniger als wenn wir die Adjazenzmatrixdarstellung verwenden, und ich vermute, dass es weniger als die Instanzgröße ist, unabhängig davon, welche vernünftige Codierung wir für den kubischen Graphen verwenden. n 22|E|n2
Marzio De Biasi
8

Ich kam mit einigen ganz natürlichen NP-vollständigen Problemen zurecht, die anscheinend lange Zeugen erfordern. Die durch die Ganzzahlen und parametrisierten Probleme lauten wie folgt:DCD

Eingabe: Ein Ein-Band TM Frage: Gibt es ein , so dass bei einer Eingabe der Länge mehr als Schritte ?n N M C n + D nM
nNMCn+Dn

Manchmal ist die Komplementarität des Problems leichter festzustellen: Läuft ein gegebenes Ein-Band-TM in der Zeit , d.h. macht es höchstens Schritte auf allen Eingängen der Größe , für alle ?C n + D C n + D n nMCn+DCn+Dnn

Das vollständige Ergebnis finden Sie hier . Grundsätzlich wird gezeigt, dass, wenn wir überprüfen möchten, ob ein Ein-Band-TM in der Zeit läuft , dies nur für Eingaben mit einer durch begrenzten Länge überprüft werden muss , wobei die Zahl ist von Zuständen des Eingangs TM. Der Zeuge wäre also die Eingabe der Länge für die die Zeitgrenze verletzt wird. In der Literaturstelle wird auch gezeigt, dass diese Probleme für alle und NP-vollständig sind .q O ( C ) q q O ( C ) C 2 D 1Cn+DqO(C)qqO(C)C2D1

Wenn der Zeuge eine Eingabe ist, die die Laufzeit verletzt, muss er im Allgemeinen die Länge . Und die Eingabe hat die Länge .qΩ(C)O(q2)

David G
quelle
3
Vielen Dank! Aber um ehrlich zu sein, finde ich "natürlicher" (ich weiß, es ist kein formales Konzept) das Problem: "Wenn eine Formel , entscheide, ob sie mindestens befriedigende Zuordnungen hat" :-)φ|φ|2
Marzio De Biasi
Ich verstehe :). Andererseits hat das Problem über die Länge des Zeugen in der Frage, während das Problem über TMs die Länge des Zeugen im Beweis erhält. Darüber hinaus wird die Länge des Zeugen nicht absichtlich in das Problem einbezogen. φ
David G
7

Hier ist ein Beispiel, das ein natürliches Problem darstellt.

Instanz: Positive ganze Zahlen, und , alle von oben durch .d1,,dnkn

Frage: Gibt es einen farbigen Graphen mit der Gradfolge d 1 , , d n ?kd1,,dn

Hier kann die Eingabe mit Bits beschrieben werden, aber der Zeuge benötigt möglicherweise Bits.O(nLogn)Ω(n2)

Bemerkung: Ich habe keinen Hinweis darauf, dass dieses spezielle Problem tatsächlich NP-vollständig ist. Das Erfordernis der Färbbarkeit könnte jedoch durch jede andere NP-vollständige Bedingung ersetzt werden; Das Problem wird unter bestimmten Umständen wahrscheinlich NP-vollständig sein, wenn dies nicht der Fall ist.k

Andras Farago
quelle
Für mich hat dieses Problem die falsche Art von Struktur, NP-vollständig zu sein, es sei denn, P = NP. Die durch jede Gradfolge definierten Klassen von Graphen können sehr groß sein, und viele von ihnen können aus trivialen Gründen farbige Elemente aufweisen. n
András Salamon
@ AndrásSalamon Tatsächlich weiß ich nicht, wie komplex dieses Problem ist oder ob es NP-vollständig gemacht werden kann, indem eine geeignete Bedingung anstelle der Färbbarkeit gewählt wird. Andererseits wäre ich überrascht, wenn für jede polyzeitprüfbare Eigenschaft Q das folgende Problem in P auftreten würde : Gibt es einen Graphen mit einer gegebenen Gradfolge, so dass er auch die Eigenschaft Q hat ? kQ.Q.
Andras Farago
Ich stimme zu, dass es unwahrscheinlich erscheint, dass Gradfolge + Eigenschaft immer in P ist, aber vielleicht sind einige davon Kandidaten für den NP-Zwischenstatus?
András Salamon
@ AndrásSalamon Ja, ich kann mir sehr gut vorstellen, dass einige von ihnen NPI-Status haben.
Andras Farago
6

Vielleicht ist dies ein dummer "Grund / Erklärung", aber für viele NP-Complete-Probleme ist eine Lösung eine Teilmenge der Eingabe (Rucksack, Scheitelpunktabdeckung, Clique, dominierende Menge, unabhängige Menge, maximaler Schnitt, Teilmengen-Summe, ...). ) oder eine Permutation oder Zuordnung zu einer Teilmenge der Eingabe (Hamilton-Pfad, Handlungsreisender, SAT, Graphisomorphismus, Graphfärbung, ...).

Wir könnten versuchen, mehr darüber zu lesen, oder uns einen ausgeklügelteren Grund einfallen lassen, aber ich bin mir nicht sicher, ob etwas Tieferes im Gange ist oder nicht.

usul
quelle
Ich denke, das ist in der Tat eine gute "erste Idee". Manchmal können die Probleme nicht eindeutig klassifiziert werden. Beispielsweise könnte SAT auch ein Teilmengenproblem sein ("Wählen Sie eine Teilmenge der wahren Variablen"). Oder ist HAMCYCLE ein Permutationsproblem bei Eckpunkten oder ein Teilmengenproblem bei Kanten? (Übrigens, vielleicht könnten die "Zuweisungsprobleme" wirklich "Partitionsprobleme" sein, sagen wir 3-Farben).
Juho
3

Was Ihre erste Frage betrifft, so gibt Allender (in " Verstärkung der unteren Schranken durch Selbstreduzierung" ) an, dass kein natürliches NP-vollständiges Problem außerhalb von NTIME (n) bekannt ist. Dies bedeutet, dass alle bekannten natürlichen NP-vollständigen Sätze Zeugen linearer Größe haben.

Mohammad Al-Turkistany
quelle
1
Es ist zu beachten, dass die Länge des längsten Akzeptanzpfades in einer nicht deterministischen Turing-Maschine der Größe des Zeugen entspricht.
Mohammad Al-Turkistany
1

Betrachten Sie die folgende Variante des MAXCLIQUE- Problems.

Instanz: Eine Schaltung mit 2 n Eingangsbits und einer polynomisch begrenzten Größe in n . Diese Schaltung bestimmt implizit einen Graphen auf 2 n Eckpunkten, so dass jeder Eckpunkt mit einer n- Bit-Zeichenfolge identifiziert wird und zwei Eckpunkte mit einer Kante verbunden werden, wenn die 2 n- Bit-Zeichenfolge, die durch Verketten der beiden Eckpunkt-IDs erhalten wird, lautet lassener C . Lassen Sie G ( C ) diese Grafik bezeichnen. Man beachte, dass es in n exponentiell viele Eckpunkte hat , aber immer noch durch die polynomiale Größenbeschreibung von C bestimmt wird .C2nn2nn2nCG(C)nC

Frage: Enthält eine Clique der Größe n k , wobei k eine feste Konstante ist?G(C)nkk

Anmerkungen:

  1. Das Problem ist NP-vollständig. Die Einschließung in ist offensichtlich. Vollständigkeits kann , dass durch die Beobachtung bewiesen werden , wenn die Schaltung nur akzeptiert Knotenpaare in dem jede ID ist höchstens N = 2 n k , dann G ( C ) kann eine beliebige sein N -eckiges Graph plus viele isolierten Knoten. (Jeder solche N- Vertex-Graph kann in C codiert werden , da C eine Polynomgröße in n und damit auch in N haben darf .) Dann lautet die Frage: Gibt es eine N / 2- große Clique in N ?NPN=2nkG(C)NNCCnNN/2N-vertex graph? Dies ist bekannt NP-vollständig, für General werden . Das Problem , dass N nicht beliebig ist, es beschränkt ist N = 2 n k , kann durch geeignete Polsterung beseitigt werden.NNN=2nk

  2. Der natürliche Zeuge für das ursprüngliche Problem ist die -sized Clique, die durch einen beschrieben werden kann O ( n k + 1 ) langen Zeichenfolge (ein n -Bit - String für jeden des n k Vertices). Beachten Sie, dass k eine sehr große Konstante sein kann, sodass der Zeuge viel länger als linear sein kann. (Auch wenn die Eingabegröße die Beschreibung von C anstelle von n ist , kann dieser Zeuge noch viel länger sein, da k unabhängig von C gewählt werden kann .)nkO(nk+1)nnkkCnkC

  3. Das Problem kann als natürlich angesehen werden, da es sich um eine Variante von MAXCLIQUE handelt .

  4. Als Allender schrieb, dass "kein natürliches NP-vollständiges Problem außerhalb von liegt" (siehe Verstärken der unteren Schranken durch Selbstverkleinerung , Abschnitt 7), hatte er möglicherweise ein engeres Konzept von Natürlichkeit im Auge. Zum Beispiel könnte natürlich auf etwas eingegrenzt werden, das die Menschen aufgrund unabhängiger, praktischer Motivationen wirklich lösen wollen. Es reicht nicht aus, wenn das Problem nicht durch Diagonalisierung konstruiert wird.NTIME(n)

Andras Farago
quelle
Ich bin nicht sicher, ob ich Ihrer Reduktion von Half-Clique auf dieses Problem folge, um die Vollständigkeit in NP festzustellen. Auf welche Schaltung wird bei einer vertex-Instanz von Half-Clique abgebildet? n
András Salamon
@ AndrásSalamon Sei ein N = 2 n k -Vertex-Graph, der als Eingabegraph für Half-Clique dient. Dann ist C die Schaltung, die ein Knotenpaar ( u , v ) akzeptiert , wenn u N ,GN=2nkC(u,v) (als Binärzahlen) und ( u , v ) E ( G ) , sonstlehnt C ab. (Dieser C . Kann als ein Polynom Größe Schaltung implementiert werden) dann G ( C ) enthält G ' auf den ersten N Knoten plus 2 n - N zusätzlichen isolierten Knoten. Der Graph G ( C ) hatgenau danneine Clique der Größe n k , wenn G 'uN,vN(u,v)E(G)CCG(C)GN2nNG(C)nkGhat eine halbe Clique.
Andras Farago