Apakah teorema hierarki ruang menggeneralisasi ke perhitungan yang tidak seragam?

Satu "hierarki ruang" yang tidak seragam yang dapat kita buktikan adalah hirarki ukuran untuk program percabangan . Untuk fungsi Boolean , misalkan menunjukkan ukuran terkecil dari komputasi program percabangan . Dengan argumen yang analog dengan argumen hierarki ini untuk ukuran sirkuit , orang dapat menunjukkan bahwa ada konstanta jadi untuk setiap nilai , ada fungsi sedemikian rupa sehingga . $f: \{0, 1\}^n \to \{0, 1\}$ $B(f)$ $f$ $\epsilon, c$ $b \leq \epsilon \cdot 2^n / n$ $f: \{0, 1\}^n \to \{0, 1\}$ $b - cn \leq B(f) \leq b$

Saya pikir memisahkan dari akan sulit. Ini sama dengan membuktikan bahwa beberapa bahasa di memiliki kompleksitas program percabangan super polinomial. Argumen menunjukkan sederhana yang tidak telah tetap -polynomial-size bercabang program: $\mathbf{PSPACE}/\text{poly}$ $\mathbf{L}/\text{poly}$ $\mathbf{PSPACE}$ $\mathbf{PSPACE}$

Dalil. Untuk setiap konstanta , ada bahasa sehingga untuk semua cukup besar , . (Di sini adalah fungsi indikator untuk .) $k$ $L \in \mathbf{PSPACE}$ $n$ $B(L_n) > n^k$ $L_n$ $L \cap \{0, 1\}^n$

Bukti. Dengan hierarki yang kami buktikan, ada program percabangan dengan ukuran yang menghitung fungsi dengan . Dalam ruang polinomial, kita dapat beralih di atas semua program percabangan ukuran , semua program percabangan ukuran , dan semua input panjang untuk menemukan program percabangan . Kemudian kita dapat mensimulasikan untuk menghitung . $P$ $n^{k + 1}$ $f$ $B(f) > n^k$ $n^{k + 1}$ $n^k$ $n$ $P$ $P$ $f$

William Hoza
sumber

Apakah teorema hierarki ruang menggeneralisasi ke perhitungan yang tidak seragam?

Jawaban: