Ist die Größe der Zeugenmitgliedschaft für jede NP-Sprache bereits bekannt?

Die Frage kam mir, als ich von Dana Moshkovitz eine Antwort auf ein anderes Thema erhielt .

Sei eine NP- Sprache und sei die jeweilige NP- Beziehung. Wir wissen, dass es ein Polynom so dass: $L$ $R_L$ $p$

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

Die obige Aussage setzt nur die Existenz eines solchen , erzwingt jedoch keine explizite Bestimmung . Im Gegensatz dazu ist für jede NP- Sprache, die ich kenne, bereits bekannt: $p$ $p$

Für SAT entspricht die Größe des Zeugen der Anzahl der Atome, die in der Formel vorkommen.
Für Hamiltonicity ist die Größe des Zeugen $O(|V|)$ , wobei $V$ die Scheitelmenge ist.
Für Grafik 3-Coloring ist die Größe des Zeugen , wobei die Scheitelpunktmenge ist. $O(|V|)$ $V$

Gibt es eine NP- Sprache (auch eine künstliche), für die wir wissen, dass es ein Polynom , das die Größe des Zeugen begrenzt, aber wir können nicht explizit bestimmen ? $p$ $p$

cc.complexity-theory np MS Dousti
quelle

Für jede Sprache in NP gibt es viele NP-Beziehungen, die dazu führen. Sind Sie Sprachen fragen , wo die minimale Polynom unbekannt ist (das heißt, wo wir versuchen können , das Polynom zu minimieren , indem sie an verschiedenen Beziehungen sucht, die zu der gleichen

) oder über Beziehungen , wo die entsprechende Polynom

unbekannt ist (aber wir wissen, dass es eine gibt)?

L

$L$

p

$p$

L

$L$

p

$p$

Joshua Grochow

@Joshua: Ich könnte Ihren Kommentar falsch verstehen, aber wenn wir das minimale

über alle Beziehungen für ein NP-vollständiges Problem kennen und es nicht Null ist, bedeutet das nicht

p

$p$

P \neq N P

$P\neq NP$

Cong Han

@ Kong: Du hast recht. Ich denke, ich meinte das Minimum, das wir kennen , zum Beispiel Modulo-Standardannahmen / aktueller Stand der Technik. STOC 2010 Papier zeigt zum Beispiel, glaube ich , Ryan Williams , dass wenn es eine Beziehung für SAT mit Zeugen Größe

o (n)

$o(n)$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

@ Joshua: Richtig, natürlich! Danke, verstanden.

Cong Han

Wenn es eine Beziehung für den Schaltkreis SAT mit der Zeugengröße

, wobei

die Anzahl der Eingaben in den Schaltkreis und

die Größe des Schaltkreises ist, dann ja,

k - ω (\log n)

$k-\omega(\log n)$

k

$k$

n

$n$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Ryan Williams

Wenn Ihnen künstliche Sprachen nichts ausmachen, können wir solche Probleme mit so ziemlich jeder Zahl k konstruieren, deren Wert Mathematikern unbekannt ist. Zum Beispiel kennen wir den Wert von R (5,5) (die fünfte Ramsey-Zahl ) oder die Größe des größten ausgeschlossenen Minors der Familie der knotenlosen Graphen nicht (diese Zahl ist aufgrund des Satzes von Robertson-Seymour endlich) ) oder der Wert von BB (10), wobei BB () für die Busy Beaver-Funktion steht . Sei k gleich einer dieser Zahlen. Wir wissen, dass k endlich ist, aber wir kennen den Wert von k nicht.

Konstruieren Sie nun ein Problem in NP, bei dem der Zeuge die Größe . Mir fällt keine gute Möglichkeit ein, das zu tun, aber hier ist eine Möglichkeit. Die Eingabe sei eine kurze Beschreibung eines Graphen. Da die Beschreibungsgröße n ist, befindet sich der Graph auf exponentiell vielen Eckpunkten. (Vielleicht ist der Eingang eine Schaltung, die zwei Eingänge x und y akzeptiert und Ihnen sagt, ob (x, y) eine Kante im Diagramm ist.) Die Frage ist, ob das Diagramm einen Pfad der Länge . Dieses Problem tritt in NP auf, weil der Prüfer die Liste der Scheitelpunkte auf dem Pfad in der Reihenfolge senden kann, die der Prüfer überprüfen kann. Die Größe des Zeugen beträgt . $O(n^k)$ $n^k$ $n^k$

Robin Kothari
quelle

Ist die Größe der Zeugenmitgliedschaft für jede NP-Sprache bereits bekannt?

Antworten: