Apakah ada teorema Time Hierarchy untuk PH?

Apakah benar bahwa ada masalah dalam hirarki dipecahkan polinomial dalam waktu (oleh bolak mesin Turing di beberapa tingkat hirarki polinomial) yang tidak larut dalam di setiap tingkat hierarki polinomial? Dengan kata lain - apakah ada teorema hierarki waktu untuk hierarki polinomial seperti yang ada pada P dan NP? Jika ada - referensi akan bagus. $O(n^k)$ $O(n^{k-1})$

Kesulitan yang saya temui adalah bahwa mesin simulasi, ketika mensimulasikan mesin dari semua level hierarki, tidak berada pada level hierarki yang berbeda. Yang mengarah ke pertanyaan terkait - apa kelas terkecil dari mesin simulasi milik? Apakah ada gunanya mendefinisikan kelas dengan bergantian (atau / )? $O(n)$ $O(\log n)$ $O(\log \log n)$

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy Yusuf
sumber

Menggunakan jumlah alternatif yang linier memberi Anda PSPACE, karena Kuantitatif Boolean Formula adalah PSPACE-complete.

Derrick Stolee

Jawaban:

Iya. Sebagai contoh, bukti biasa dari teorema hierarki waktu (dengan secara langsung mensimulasikan mesin arbitrer) dapat digunakan untuk menunjukkan bahwa untuk setiap , bukan bagian dari . Alasan untuk beralih dari ke $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$ adalah bahwa, dalam argumen diagonalisasi ini, kita harus melakukan "kebalikan" dari mesin yang kita simulasi, jadi kita harus menjalankan dalam mode universal ketika mesin simulasi berada dalam mode eksistensial, dan sebaliknya.

Anda juga bisa mendapatkan hasil seperti ini tanpa beralih dari ke : untuk setiap , bukan bagian dari . Ini dapat dilakukan dengan menggunakan bukti hierarki waktu karena Zak (referensi: " A hirarki waktu mesin Turing ", Theoretical Computer Science 26 (3): 327--333, 1983). Untuk referensi eksplisit ke versi teorema hierarki waktu ini, lihat Dieter van Melkebeek $\Sigma$ $\Pi$ $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$ " Sebuah Survei Batas Bawah untuk Kepuasan dan Masalah Terkait " (tersedia di halaman rumahnya).

Ryan Williams
sumber

Jawaban ini dengan sangat jelas menunjukkan keberadaan teorema hierarki waktu untuk setiap tingkat hierarki yang berbeda. Ini tidak segera menunjukkan adanya teorema untuk PH secara keseluruhan.

Joseph

Pertanyaan Anda yang lebih kuat akan sulit untuk diselesaikan secara afirmatif; itu akan berarti

. Misalkan ada

dan bahasa

dalam

yang tidak ada di

untuk setiap

. Kemudian

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

c

$c$

L

$L$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{k - 1}]

$\Sigma_d TIME[n^{k-1}]$

d

$d$

. Ini karena setiap bahasa

ada dalam

untuk beberapa

tergantung pada

(oleh argumen tipe-Savitch-theorem). Jadi, jika

maka sebenarnya setiap bahasa di

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

L \in L O G S P A C E

$L \in LOGSPACE$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

L

$L$

L O G S P A C E = N P

$LOGSPACE = NP$

Adalah di

untukbeberapa

, bertentangan dengan apa yang Anda inginkan untuk ditampilkan.

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

Ryan Williams

Jawaban untuk pertanyaan yang direvisi (revisi 4 dari pertanyaan) adalah tidak. Jika masalah keputusan L dapat dipecahkan dalam waktu O ( n ^k ) oleh mesin ∑ _i P, maka L dapat diselesaikan dalam waktu linier oleh mesin Turing dengan oracle untuk L , yang merupakan mesin ₊₁_{i +1} P. Karenanya, ∑ _i WAKTU [O ( n ^k )] ⊆ Σ _{i +1} WAKTU [O ( n )].

Tsuyoshi Ito
sumber

Tidak, ini bukan bagaimana definisi

bekerja. Jika

untuk semua

, maka

. Jika

Σ_{j} T I M E [t (n)]

$\Sigma_j TIME[t(n)]$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

N P \neq c o N P

$NP \neq coNP$

dan

untuk setiap

, biarkan

menjadi menjalankan waktu beberapa algoritma nondeterministic untuk Tautology. Maka kita memiliki

N P = c o N P

$NP = coNP$

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$

j, k

$j,k$

O (n^{c})

$O(n^c)$

, di mana inklusi pertama adalah dengan asumsi dan inklusi kedua mengikuti dari argumen simulasi standar. Ini adalah kontradiksi.

N T I M E [O (n^{c^{2}})] \subseteq Σ_{2} T I M E [O (n)] \subseteq N T I M E [O (n^{c})]

$NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$

Ryan Williams

@Ryan: Definisi yang saya gunakan adalah: L∈ΣiTIME [t (n)] iff ada bahasa O∈Σ (i − 1) P dan mesin turing n (non-deterministik) (n) waktu dengan oracle untuk O yang mengenali L. Saya pikir ini adalah definisi standar, tetapi saya tidak punya referensi untuk mendukung klaim saya. Apa definisi yang Anda gunakan?

Tsuyoshi Ito

Definisi ini:

IFF ada waktu linear predikat

sehingga

L \in Σ_{i} T I M E [t (n)]

$L \in \Sigma_i TIME[t(n)]$

R (x, y_{1}, \dots, y_{i})

$R(x,y_1,\ldots,y_i)$

benar.

x \in L ⟺ (\exists y_{1} : | y_{1} | \leq t (| x |)) \dots (\forall y_{i} : | y_{i} | \leq t (| x |)) R (x, y_{1}, \dots, y_{i})

$x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$

Ryan Williams

@Ryan: Ok, saya tidak tahu definisi itu. Jika itu yang ingin ditanyakan oleh penanya, jawaban saya tidak berlaku.

Tsuyoshi Ito