Bedeutet die Isomorphismus-Vermutung exponentielle Untergrenzen für die Dichte der Zeugen?

Die Isomorphismus-Vermutung von Berman und Hartmanis besagt, dass alle vollständigen Mengen eine polynomielle Zeit isomorph zueinander sind. Dies bedeutet, dass vollständige Probleme über polynomialzeitberechnbare und invertierbare Bijektionen effizient aufeinander reduziert werden können. Die Vermutung impliziert . $NP$ $NP$ $P\neq NP$

Die Isomorphismus-Vermutung impliziert eine exponentielle Untergrenze für die Dichte von $NP$ vollständigen Mengen, da das Problem der Erfüllbarkeit dicht ist. Ich frage mich, ob dies auch eine exponentielle Untergrenze für die Dichte der Zeugen für eine $NP$ vollständige Menge impliziert.

Bedeutet die Isomorphismus-Vermutung exponentielle Untergrenzen für die Dichte der Zeugen? Bedeutet dies, dass $NP$ vollständige Probleme nicht in $FewP$ ?

Das beste mir bekannte Ergebnis ist das Folgende:

Wenn $P=UP$ und $NP=EXP$ die Isomorphismus-Vermutung .

Die Dichte $D$ einer Menge $S$ bezieht sich auf die Anzahl der Zeichenfolgen mit einer Länge von weniger als $n$ in der Sprache. Eine Menge $S$ ist exponentiell dicht, wenn ihre Dichte $D=\Omega(2^{n^\epsilon})$ für einige $\epsilon \gt 0$ und für unendlich viele $n$ und spärlich, wenn $D$ = $O(poly(n))$ .

cc.complexity-theory structural-complexity Mohammad Al-Turkistany
quelle

Die Zeugen-Dichte der Menge hängt von der maximalen Anzahl von Zeugen für über alle .

X

$X$

x

$x$

x \in X

$x \in X$

Mohammad Al-Turkistany

Scheint unwahrscheinlich. Es wäre interessant, ein Orakel zu konstruieren, in dem die Isomorphismus-Vermutung gilt und oder ... (Beachten Sie, dass die Herstellung von das Leben in dieser Konstruktion etwas erschweren kann, da die Isomorphismus-Vermutung gültig ist man würde dann brauchen und noch einen anderen Weg um die Joseph-Young-Vermutung herum brauchen.)

N P = U P

$NP=UP$

N P = F e w P

$NP=FewP$

N P = U P

$NP=UP$

P \neq U P

$P \neq UP$

Joshua Grochow

Ich sehe nicht ein, wie das unmittelbar folgen würde: Die Isomorphismus-Vermutung handelt von Sprachen und scheint keine Auswirkungen auf die Zeugenstruktur von NP-Verifizierern zu haben. (Jede Sprache hat unendlich viele verschiedene Verifizierer, und Sie könnten diese Verifizierer möglicherweise manipulieren, um seltsame Dinge zu tun.)

Ihre Frage enthüllt jedoch eine weitere sehr natürliche, faszinierende Frage zur folgenden Stärkung der Isomorphismus-Vermutung:

"Sind alle Verifizierer für NP-vollständige Mengen polyzeitlich isomorph?"

Das heißt, wir wollen nicht nur einen mehrzeitigen Isomorphismus zwischen zwei beliebigen NP-vollständigen Sprachen die durch die Verifizierer , sondern auch Isomorphismen zwischen ihre Mengen von Eingabe-Zeugen-Paaren, die den Isomorphismus . (Hinweis: Es gibt mehrere Möglichkeiten, dies formal zu definieren.) Alle Härtebeweise, die ich mir vorstellen kann, geben Ihnen auch eine Eins-zu-Eins-Korrespondenz dieser Art. Diese stärkere "Zeugen-Isomorphismus-Vermutung" würde eine Art Ja-Antwort auf Ihre Frage implizieren. $\phi_{L,L'}$ $L,L'$ $V,V'$ $\psi_{V,V'}$ $\phi_{L,L'}$ $NP$

Eine schnelle Google-Suche (Eingabe von "Zeugen-Isomorphismus-Vermutung") ergab eine Übersicht über einige Ansätze für diese Art von Frage:

Eric Allender. Untersuchungen zur Struktur vollständiger Mengen. Perspektiven in der Computerkomplexität: The Somenath Biswas Anniversary Volume, Springer, 2014

Ryan Williams
quelle

+1 Sehr interessant. Auf Ihren Vorschlag hin habe ich gegoogelt und dieses Papier, Zeugen-isomorphe Reduktionen und das lokale Suchproblem gefunden . Ist dies die Art des erforderlichen Zeugenisomorphismus ?

Mohammad Al-Turkistany

Interessant! Haben Sie , dass für jedes sagen will'die -komplette, gibt es Verifizierer und kompatibel Isomorphien ? Oder gibt es wirklich für jedes Paar von Verifizierern kompatible Isos? Da Ihre Vorstellung von kompatiblen Isos insbesondere sparsame Reduzierungen in beide Richtungen impliziert, ist die zweite Frage leicht zu verfälschen: Nehmen Sie einen beliebigen Prüfer für SAT und lassen Sie einen Prüfer für SAT sein, der jeden Zeugen in akzeptiert .

L, L^{'}

$L,L'$

N P

$\mathsf{NP}$

V, V^{'}

$V,V'$

ϕ_{L, L^{'}}, ψ_{V, V^{'}}

$\phi_{L,L'}, \psi_{V,V'}$

V, V^{'}

$V,V'$

V

$V$

V^{'}

$V'$

{{0, 1}^{n} w | V (w) = 1}

$\{\{0,1\}^n w | V(w)=1\}$

Joshua Grochow

Richtig, Sie müssen vorsichtig sein, wie Sie die Vermutung formulieren, um triviale Gegenbeispiele zu vermeiden. Googeln hat mir gezeigt, dass ich nicht der erste bin, also schlage ich vor, die Arbeit von Leuten zu lesen, die länger als 10 Minuten darüber nachgedacht haben :)

Ryan Williams

Ryan, ich denke deine Vermutung ist sehr wichtig. Es ist möglicherweise einfacher zu beweisen als die Standard-Isomorphismus-Vermutung von Berman und Hartmanis. Ich denke, Ihre Vermutung legt die Existenz eines universellen Verifizierers für alle NP-Sätze nahe.

Mohammad Al-Turkistany

Bedeutet die Isomorphismus-Vermutung exponentielle Untergrenzen für die Dichte der Zeugen?

Antworten: