Apa yang

Hal ini terkait dengan pertanyaan, Apakah Ukuran Keanggotaan Saksi untuk Setiap Bahasa NP Sudah Diketahui?

Beberapa masalah $\mathsf{NP}$ (-complete) alami memiliki saksi panjang linier: tugas yang memuaskan untuk $SAT$ , urutan simpul untuk $HAMPATH$ , dll.

Pertimbangkan kelas kompleksitas " $\mathsf{NP}$ terbatas pada saksi panjang linier". Definisi formal dari kelas kompleksitas ini, sebut saja $\mathcal{C}$ : $L\in\mathcal{C}$ jika . $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$

Apakah ini kelas kompleksitas yang diketahui? Apa saja propertinya?

cc.complexity-theory complexity-classes np argentpepper
sumber

Tidak bisakah Anda selalu mencapainya dengan melapisi?

KIA

Sebagai KIA menunjukkan, jika

adalah setiap

bahasa dengan saksi dari ukuran

, maka

adalah

bahasa dengan saksi linear-ukuran, dan

dan

adalah polinomial-waktu banyak-satu setara. Kelas Anda tidak cukup

L

$L$

N P

$\mathsf{NP}$

O (n^{k})

$O(n^k)$

p a d (L) := {x 10^{| x |^{k}} : x \in L}

$pad(L) := \{ x10^{|x|^{k}} : x \in L\}$

N P

$\mathsf{NP}$

L

$L$

p a d (L)

$pad(L)$

N P

$\mathsf{NP}$ , tapi pada dasarnya sama. Kelas Anda menyarankan tidak tertutup di bawah polytime banyak-satu pengurangan, tetapi untuk setiap

ada beberapa bahasa di kelas Anda yang polytime banyak-satu setara dengan

L

$L$

N P

$\mathsf{NP}$

L

$L$

Joshua Grochow

Jawaban:

Kelas yang Anda usulkan mungkin bukan . (Jika , maka setiap bahasa akan memiliki saksi ukuran linier, yang akan menyiratkan bahwa setiap dan , antara lain) . ${\cal C}$ $NP$ ${\cal C} = NP$ $NP$ $NP \subseteq TIME[2^{O(n)}]$ $NP \neq EXP$

Sangat alami untuk mempertimbangkan kelas-kelas semacam itu; mereka muncul dalam beberapa pengaturan. Dalam makalah ini , Rahul Santhanam (implisit) mengusulkan notasi untuk waktu- perhitungan dengan bit -guess. Karenanya . Dalam tulisan ini $TIGU(t(n),g(n))$ $t(n)$ $g(n)$ ${\cal C} = \bigcup_{k} TIGU(n^k,kn)$ , Saya mendefinisikan kelas analog . (NTIBI singkatan dari "waktu nondeterministic dan bit".) Juga, Cai dan Chen akan memanggil kelas Anda (GC singkatan dari "Tebak dan Periksa", lih L. Cai dan J. Chen Tentang jumlah nondeterminisme dan kekuatan verifikasi. SIAM Journal on Computing, 1996). Akhirnya, jika Anda mencari "nondeterminisme terbatas" Anda mungkin menemukan tiga notasi lagi untuk kelas yang sama ... $NTIBI[t(n),b(n)]$ $GC(O(n), P)$

Ryan Williams
sumber