Was sind die Komplexitäten der folgenden SAT-Untergruppen?

Angenommen, $P \neq NP$

Verwenden Sie die folgende Notation für tetration (dh. ${}^ia$ ). ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$

| x | ist die Größe der Instanz x.

Sei L eine Sprache, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

Was ist die Komplexität der folgenden Sprachen:

$L_1 = SAT|_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$ $L_2 = SAT|_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

Da , können sie unter der Annahme, dass ist, nicht beide in . Da beide exponentielle Löcher haben, glaube ich nicht, dass SAT auf eins reduziert werden kann. $L_1 \sqcup L_2 = SAT$ $P \neq NP$

Daher wäre die Intuition, dass sie beide im NPI sind, aber ich kann keinen Beweis oder Beweis finden.

Zwei weitere Sprachen sind $L_3 = SAT|_{|x|={}^{2i+1}2}$ $L_4 = SAT|_{|x|={}^{2i}2}$

Wenn sich einer von beiden im NPC befindet, befindet sich der andere in P, da er für jede Instanz des einen nicht in eine größere Instanz des anderen umgewandelt werden kann, da er exponentiell groß ist und kleinere Instanzen eine logarithmische Größe haben. Noch aus Intuition gibt es keinen Grund, warum sie eine andere Komplexität haben würden. Was wäre ihre Komplexität?

Ladners Beweis für NPI-Probleme unter der Annahme von verwendet Sprachen wie oder , aber und werden nicht durch Diagonalisierung erstellt. $P \neq NP$ $L_1$ $L_2$ $L_1$ $L_2$

cc.complexity-theory np-hardness complexity-classes Ludovic Patey
quelle

Ihre Sprachen haben viele Instanzen, die durch zusätzliche Klauseln aufgefüllt werden, die nicht miteinander interagieren. Sie scheinen daher nach Schönings Diagonalisierungsargument NPI zu sein? dx.doi.org/10.1016/0304-3975(82)90114-1

András Salamon

Nach "sie können nicht beide in P sein" sollte es "unter der Annahme, dass P

NP ..."

\neq

$\ne$

Emil

Ich habe "unter der Annahme" hinzugefügt, auch wenn ich diese Annahme bereits zuvor festgelegt habe.

Ludovic Patey

Wenn entweder L1 oder L2 NP-vollständig ist, schlägt die Isomorphismus-Vermutung fehl, da weder L1 noch L2 ein Zylinder sind (eine Auffüllfunktion haben). So beweisen , dass einer von ihnen ist NP-vollständig erfordert nicht-Relativierung Techniken. Ich sehe noch kein Hindernis dafür, zu zeigen, dass einer von ihnen nicht NP-vollständig ist.

Joshua Grochow

Ich war vielleicht etwas unklar mit meinen Quantifizierern. Lassen Sie mich Klammern hinzu: es keinen Poly-Zeit Orakel Maschine existiert

, so dass [für alle

[

löst

]]. Das heißt, für jedes

kann es sein, dass für einige X

eine der Sprachen löst, aber es kann nicht für alle

zutreffen . So könnte beispielsweise

ohne das Orakel

(nicht relativiert) lösen , aber egal was

M

$M$

X

$X$

M^{X}

$M^X$

L_{1}^{X} o r L_{2}^{X}

$L_1^X or L_2^X$

M

$M$

M^{X}

$M^X$

X

$X$

M

$M$

L_{1}

$L_1$

M

$M$ ist, es wird ein Orakel geben, so dass es keine der beiden Sprachen löst.

Joshua Grochow

Ich denke, beide sind NPI unter der stärkeren Annahme (aber offensichtlich wahr), dass NP nicht in "unendlich oft P" ist - dh jeder Polynomzeitalgorithmus A und jedes ausreichend große n, A kann SAT bei Eingaben der Länge n nicht lösen.

In diesem Fall sind solche Sprachen nicht in P, aber sie können auch nicht NP-vollständig sein, da andernfalls eine Reduktion von SAT auf eine Sprache L mit großen Löchern einen Algorithmus für SAT ergibt, der auf diesen Löchern erfolgreich ist.

Eine solche Annahme ist auch notwendig, da die Sprachen ansonsten in P oder NP-vollständig sein können, je nachdem, wo sich die "einfachen Eingabelängen" befinden.

Boaz Barak
quelle

@Boaz: Ich verstehe irgendwie, was Sie unter "eine solche Annahme ist notwendig" verstehen, aber ich habe Probleme, die Notwendigkeit zu formalisieren. Ich denke man ein Oracle - Konstrukt

, ohne allzu große Schwierigkeiten, so daß

, eine Maschine poly-Zeit

, so dass

entscheidet

auf unendlich viele Eingangslängen, aber

und

sind

-zwischen.

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

M

$M$

M^{X}

$M^X$

S A T^{X}

$SAT^X$

L_{1}^{X}

$L_1^X$

L_{2}^{X}

$L_2^X$

N P^{X}

$NP^X$

Joshua Grochow

N P \neq P

$NP\neq P$

N P \neq P

$NP\neq P$

L_{1}

$L_1$

L_{1}

$L_1$

P

$P$

L_{2}

$L_2$

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

L_{1}^{X} \in P

$L_1^X \in P$

L_{1}^{X} \in P

$L_1^X\in P$

M

$M$

L_{1}^{X}

$L_1^X$

M

$M$

L_{1}

$L_1$

X

$X$

P_{1} \in P

$P_1\in P$

M \in P^{X}

$M\in P^X$

S A T^{X}

$SAT^X$

X

$X$

S A T

$SAT$

X

$X$

X

$X$

S A T^{X}

$SAT^X$

Was sind die Komplexitäten der folgenden SAT-Untergruppen?

Antworten: