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 , aber $O(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 ? $n$ $n$

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

$L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
$L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ 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?

cc.complexity-theory np proof-complexity 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?

Θ (n \log n)

$\Theta(n \log n)$

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 \times n

$n \times 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

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$ $n^2$ $n^2\log n$

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.

2 | E |

$2|E|$

n^{2}

$n^2$

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: $C$ $D$

Eingabe: Ein Ein-Band TM Frage: Gibt es ein , so dass bei einer Eingabe der Länge mehr als Schritte ? $M$
$n\in\mathbb{N}$ $M$ $Cn+D$ $n$

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 ? $M$ $Cn+D$ $Cn+D$ $n$ $n$

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 . $Cn+D$ $q^{O(C)}$ $q$ $q^{O(C)}$ $C\geq 2$ $D\geq 1$

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^{\Omega(C)}$ $O(q^2)$

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" :-)

φ

$\varphi$

| φ |^{2}

$|\varphi|^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.

φ

$\varphi$

David G

7

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

Instanz: Positive ganze Zahlen, und , alle von oben durch . $d_1,\ldots,d_n$ $k$ $n$

Frage: Gibt es einen farbigen Graphen mit der Gradfolge ? $k$ $d_1,\ldots,d_n$

Hier kann die Eingabe mit Bits beschrieben werden, aber der Zeuge benötigt möglicherweise Bits. $O(n\log n)$ $\Omega(n^2)$

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

$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

das folgende Problem in P auftreten würde : Gibt es einen Graphen mit einer gegebenen Gradfolge, so dass er auch die Eigenschaft

?

k

$k$

Q

$Q$

Q

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

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

Anmerkungen:

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 , dann kann eine beliebige sein -eckiges Graph plus viele isolierten Knoten. (Jeder solche Vertex-Graph kann in codiert werden , da eine Polynomgröße in und damit auch in haben darf .) Dann lautet die Frage: Gibt es eine große Clique in ? $NP$ $N=2n^k$ $G(C)$ $N$ $N$ $C$ $C$ $n$ $N$ $N/2$ $N$ -vertex graph? Dies ist bekannt NP-vollständig, für General werden . Das Problem , dass nicht beliebig ist, es beschränkt ist , kann durch geeignete Polsterung beseitigt werden. $N$ $N$ $N=2n^k$
Der natürliche Zeuge für das ursprüngliche Problem ist die -sized Clique, die durch einen beschrieben werden kann langen Zeichenfolge (ein -Bit - String für jeden des Vertices). Beachten Sie, dass 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 anstelle von , kann dieser Zeuge noch viel länger sein, da unabhängig von .) $n^k$ $O(n^{k+1})$ $n$ $n^k$ $k$ $C$ $n$ $k$ $C$
Das Problem kann als natürlich angesehen werden, da es sich um eine Variante von MAXCLIQUE handelt .
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

$n$

András Salamon

@ AndrásSalamon Sei

ein

-Vertex-Graph, der als Eingabegraph für Half-Clique dient. Dann ist

die Schaltung, die ein Knotenpaar

akzeptiert , wenn

G^{'}

$G'$

N = 2 n^{k}

$N=2n^k$

C

$C$

(u, v)

$(u,v)$

(als Binärzahlen) und

, sonstlehnt

ab. (Dieser

. Kann als ein Polynom Größe Schaltung implementiert werden) dann

enthält

auf den ersten

Knoten plus

zusätzlichen isolierten Knoten. Der Graph

hatgenau danneine Clique der Größe

, wenn

u \leq N, v \leq N

$u\leq N, \; v\leq N$

(u, v) \in E (G^{'})

$(u,v)\in E(G')$

C

$C$

C

$C$

G (C)

$G(C)$

G^{'}

$G'$

N

$N$

2^{n} - N

$2^n-N$

G (C)

$G(C)$

n^{k}

$n^k$

G^{'}

$G'$ hat eine halbe Clique.

Andras Farago

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

Antworten: