Apakah ada masalah NP-Complete (atau NP-Intermediate) yang diketahui dalam ruang nlineterministic sublinear?

9

Ada beberapa masalah NP-Lengkap ( , , dll.) Diketahui berada di . Bagaimana dengan ruang sub-linear? $\mathsf{SAT}$ $\mathsf{SUBSETSUM}$ $\mathsf{DSPACE(n)}$

Apakah ada masalah NP-Complete (atau NP-Intermediate) yang diketahui dalam ruang nlineterministic sublinear ?

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

14

Versi planar dari banyak masalah NP-complete milik untuk beberapa $NTISP(n,n^q)$ $q<1$

Lihat misalnya " Batas Bawah dan Masalah Lengkap dalam Kelas Waktu Kompleksitas Linear Nondeterministik dan Ruang Sublinear " oleh P. Chapdelaine dan E. Grandjean (2006)

Marzio De Biasi
sumber

Terima kasih! Apakah Anda punya ide tentang ruang poli-logaritmik?

Abuzer Yakaryilmaz

14

Setiap masalah memiliki versi seperti itu, PAD saja! Misalnya bahasa yang terdiri dari 3CNF panjang m yang benar diikuti oleh m ^ 2 0 adalah dalam DSPACE (sqrt (n)).

domotorp
sumber

Terima kasih! Apakah Anda punya ide tentang ruang poli-logaritmik?

Abuzer Yakaryilmaz

1

cukup letakkan 3CNF dengan

nol?

2^{\sqrt{n}}

$2^{\sqrt{n}}$

Sasho Nikolov

2

@ Sasho: Maka masalahnya akan berhenti menjadi NP-lengkap, Anda hanya bisa PAD dengan jumlah poli nol.

domotorp

1

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

$2^{poly-log}$

@domotorp: Ya, Anda benar! Terima kasih!

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
sumber

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)}$

Apakah ada masalah NP-Complete (atau NP-Intermediate) yang diketahui dalam ruang nlineterministic sublinear?

Jawaban: