Gibt es ein bekanntes NP-Complete- (oder NP-Intermediate-) Problem im sublinearen nichtdeterministischen Raum?

9

Es gibt einige NP-vollständige Probleme ( , usw.), von denen bekannt ist, dass sie in . Was ist mit den sublinearen Räumen? $\mathsf{SAT}$ $\mathsf{SUBSETSUM}$ $\mathsf{DSPACE(n)}$

Gibt es ein bekanntes NP-Complete- (oder NP-Intermediate-) Problem im sublinearen nichtdeterministischen Raum?

cc.complexity-theory np-hardness nondeterminism np-intermediate Abuzer Yakaryilmaz
quelle

14

Die planare Version vieler NP-vollständiger Probleme gehört für einige zu $NTISP(n,n^q)$ $q<1$

Siehe zum Beispiel " Untere Grenzen und vollständige Probleme in nichtdeterministischen linearen Zeit- und sublinearen Raumkomplexitätsklassen " von P. Chapdelaine und E. Grandjean (2006)

Marzio De Biasi
quelle

Vielen Dank! Haben Sie eine Vorstellung vom polylogarithmischen Raum?

Abuzer Yakaryilmaz

14

Jedes Problem hat eine solche Version, einfach PAD! ZB ist die Sprache, die aus einem echten 3CNF der Länge m gefolgt von m ^ 2 0 besteht, in DSPACE (sqrt (n)).

domotorp
quelle

Vielen Dank! Haben Sie eine Vorstellung vom polylogarithmischen Raum?

Abuzer Yakaryilmaz

1

2^{\sqrt{n}}

$2^{\sqrt{n}}$

2

@Sasho: Dann würde das Problem aufhören, NP-vollständig zu sein, Sie können nur mit einer Polyzahl von Nullen PAD.

Domotorp

1

2^{p o l y - l o g}

$2^{poly-log}$

@domotorp: Ja, du hast recht! Vielen Dank!

Abuzer Yakaryilmaz

11

$\mathsf{NP}$ $O(\log n)$ $\mathsf{NP}$ $\mathsf{NP}$ $L$ $M$ $x \in L$ $y$ $M(x, y)$ $x$ $y$ $M$ $x, y$ $M$ $x \not \in L$ $y$ $M(x, y)$

$\mathsf{NP} = \mathsf{NL}$ $\mathsf{NP} = \mathsf{P}$ $\mathsf{NL}$

Sasho Nikolov
quelle

D S P A C E (2^{n}) \subseteq I P (1)

$DSPACE(2^n) \subseteq IP(1)$

1

N P

$\mathsf{NP}$

N P

$\mathsf{NP}$

4

N S P A C E_{o f f - l i n e} (l o g)

$\mathsf{NSPACE_{off\mbox{-}line}(log)}$

N P = N S P A C E_{o f f - l i n e} (l o g)

$\mathsf{NP} = \mathsf{NSPACE_{off\mbox{-}line}(log)}$

N L = N S P A C E_{o n - l i n e} (l o g)

$\mathsf{NL} = \mathsf{NSPACE_{on\mbox{-}line}(log)}$

Gibt es ein bekanntes NP-Complete- (oder NP-Intermediate-) Problem im sublinearen nichtdeterministischen Raum?

Antworten: