Rumus Boolean yang terukur dengan pergantian logaritmik

Saya sedang mempelajari masalah yang sulit untuk kelas formula boolean yang dikuantifikasi dengan jumlah logaritmik dari pergantian quantifiers. Masalah di kelas ini akan terlihat seperti:

$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$

Di mana , dan adalah rumus boolean dari variabel .F x 1 … x $a_{\log n} = n$$F$$x_1 \ldots x_n$

Kelas ini jelas mengandung dan terkandung dalam . Apakah ada nama untuk kelas ini? Apakah ada yang lebih diketahui tentang itu?A P = P S P A C $PH$$AP = PSPACE$

Membangun berdasarkan jawaban Michael Wehar, tampaknya Anda dapat dengan mudah menunjukkan bahwa perhitungan dapat dikodekan dalam polysize QBFs seperti: Anda menggunakan O ( log n ) bergantian, masing-masing p o l y ( n ) bit, dan lakukan argumen yang mirip dengan teorema Savitch. Setiap dua alternatif akan membagi waktu berjalan perhitungan dengan p o l y ( $NTISP(n^{\log n},poly(n))$$O(\log n)$$poly(n)$ faktor.$poly(n)$

Saya akan memanggil kelas , mengikuti notasi dalam Fortoff's "Time-Space Tradeoffs for Satisfiability" yang juga dapat dikutip untuk argumen yang dibuat sketsa di paragraf sebelumnya (tapi silakan lihat makalah untuk referensi sebelumnya).$\Sigma_{O(\log n)} P$

(1) Apa yang sudah kita ketahui:

Seperti yang sudah Anda nyatakan, QBF dengan bergantian dari pengukur sulit untuk setiap tingkat hirarki polinomial.$\log(n)$

(2) Saya pikir kita juga bisa membuktikan yang berikut:

Masalahnya adalah -Hard.$NSPACE(log^2(n))$

(3) Inilah pembenaran informal saya atas pernyataan sebelumnya:

Mengingat ruang terikat NTM dan string masukan, kita perlu menentukan apakah ada sebuah perhitungan menerima pada string masukan yang diberikan.$log^2(n)$

Setiap konfigurasi dalam perhitungan dapat diwakili oleh dasarnya bit. Dengan kata lain, kita dapat merepresentasikan konfigurasi oleh sekelompok variabel log 2 ( n ) .$\log^2(n)$$\log^2(n)$

Idenya adalah bahwa kita memiliki konfigurasi mulai dan konfigurasi akhir dan kita perlu menebak perhitungan yang terjadi di antaranya. Kami secara rekursif menebak konfigurasi "tengah" menggunakan quantifiers yang ada dan berulang memverifikasi bahwa konfigurasi "kiri" mengarah ke konfigurasi "tengah" dan "tengah" mengarah ke "kanan" menggunakan semua kuantifiers.

Sekarang untuk membuat ini berfungsi, alih-alih memilih satu konfigurasi "tengah", kita perlu memilih sekelompok konfigurasi "perantara" yang berjarak sama antara konfigurasi "kiri" dan "kanan". Secara khusus, kita bisa menebak konfigurasi "perantara" yang sama-sama spasi menggunakan kuantifiers yang ada dengan$\sqrt{n}$variabel dan kemudian recurse pada setiap kesenjangan antara konfigurasi menggunakan untuk semua bilangan dengan kasarlog(n)variabel.$\sqrt{n} * log^2(n)$$\log(n)$

Rekursi hanya perlu melanjutkan ke kedalaman untuk dapat mencakup perhitungan panjang $2 * \log(n)$mana setiap konfigurasi memiliki paling banyaklog2(n)banyak bit.$\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$$\log^2(n)$

Karena rekursi memiliki kedalaman , kami hanya memiliki kelompok variabel O ( log ( n ) ) yaitu pergantian. Karena setiap kelompok bilangan hanya memiliki $O(\log(n))$$O(\log(n))$variabel, secara total kita memilikiO($\sqrt{n} * log^2(n)$variabel.$O(\sqrt{n} * log^3(n))$

Jangan ragu untuk memberikan umpan balik atau koreksi. Terima kasih banyak dan saya harap ini sedikit membantu.

(4) Penegasan yang lebih umum seperti yang disarankan oleh jawaban Ryan:

Anda harus dapat melakukan konstruksi sebelumnya dengan cara yang lebih umum. Pertimbangkan yang berikut ini:

Pada setiap langkah rekursi, pisahkan menjadi kelompok konfigurasi "menengah" menggunakan c ( n ) bit per konfigurasi. Kemudian, lakukan rekursi ke kedalaman d ( n ) .$g(n)$$c(n)$$d(n)$

Selama kita tidak memiliki terlalu banyak variabel dan terlalu banyak pergantian, ini tampaknya berfungsi dengan baik. Secara kasar, kita perlu yang berikut ini dipenuhi:

• $g(n) * c(n) * d(n) \leq n$
• $d(n) \leq \log(n)$

Pendekatan umum kami akan digunakan untuk mensimulasikan mesin Turing non-deterministik yang berjalan untuk langkah menggunakan c ( n ) bit memori.$g(n)^{d(n)}$$c(n)$

Secara khusus, kami memilih yang berikut:

• $g(n) = \sqrt{n}$

• $c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$

• $d(n) = 2 * \log^2(n)$

Ketidaksetaraan sebelumnya puas dan kami dapat melakukan konstruksi untuk mensimulasikan mesin Turing non-deterministik yang berjalan sekitar langkah menggunakan $2^{\log^2(n)}$ bit memori.$\frac{\sqrt{n}}{2 * log^2{n}}$

Dengan kata lain, kami memiliki hasil kekerasan yang lebih baik dari sebelumnya. Secara khusus, masalahnya sulit untuk .$NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$

(5) Generalisasi lebih lanjut:

Dalam generalisasi sebelumnya, kami mensimulasikan mesin Turing yang dibatasi waktu dan ruang. Namun, kami mungkin dapat mensimulasikan waktu dan ruang yang dibatasi oleh mesin Turing.

Biarkan saya jelaskan sedikit. Jadi kami menggunakan kira-kira alternatif untuk melakukan rekursi ke kedalaman log ( n ) . Namun, kita bisa menggunakan beberapa alternatif pada awalnya, katakanlah $\log(n)$$\log(n)$ . Kemudian, kita bisa menggunakan sisa$\sqrt{\log(n)}$ alternatif untuk menuju kedalaman$\sqrt{\log(n)}$ .$\sqrt{\log(n)}$

Dalam hal ini, kita bisa mensimulasikan mesin Turing bergantian yang memiliki bergantian dengan panjang saksi sublinear, jalankan selama2 log $\sqrt{\log(n)}$langkah, dan gunakan$2^{\log^{\frac{3}{2}}(n)}$ bit memori.$\frac{\sqrt{n}}{2 * log^2{n}}$

Dengan kata lain, masalahnya adalah sulit bagi $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ with sublinear witness lengths. Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.

Thank you for the comments and feel free to offer any further corrections or clarifications. :)

A shorter answer.

Initial observations:

• The problem is hard for every level of the polynomial hierarchy.
• The problem is hard for alternating Turing machines with $\log(n)$ alternations that run for polynomial time.

Deeper Insights:

• Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ Turing machines.
• Also, as Ryan pointed out, the problem can encode computations for $NTimeSpace(2^{\log^2(n)}, \sqrt{n})$ Turing machines.

• More generally, the problem can encode computations for machines corresponding to various classes of the form $AltTimeSpace(a(n), t(n), s(n))$ with restricted witness lengths. I'm not quite sure what the exact relationship between $a(n)$, $t(n)$, and $s(n)$ has to be, but we know that:

  1. $\; \; a(n) \leq \log(n)$

  2. $\; \; t(n) \leq 2^{\log^2(n)}$

  3. $\; \; s(n) \leq n$

See my longer answer for more details on the trade-offs between $a(n)$, $t(n)$, and $s(n)$.

Note: In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much. That is, if we blow-up from $n$ size Turing machine input to $poly(n)$ size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial. The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures $a(n)$, $t(n)$, and $s(n)$ depend on each other.