Bagaimana kita bisa mengekspresikan " " sebagai formula orde pertama? [Tutup]

1. Bagaimana kita dapat mengekspresikan " " sebagai formula orde pertama?$P=PSPACE$
2. Level hirarki aritmatika mana yang berisi rumus ini (dan apa level minimum hierarki yang diketahui saat ini yang mengandungnya)?

Untuk referensi, lihat posting blog ini oleh Lipton .

Pertama, saya ingin membahas komentar untuk pertanyaan, di mana disarankan bahwa "false" menyatakan karena pernyataan itu salah. Walaupun ini mungkin lelucon yang bagus, sebenarnya sangat berbahaya untuk berpikir seperti ini. Ketika kita bertanya bagaimana mengekspresikan kalimat tertentu dalam sistem formal tertentu, kita tidak berbicara tentang nilai-nilai kebenaran. Jika ya, maka ketika seseorang bertanya, "Bagaimana saya menuliskan fakta bahwa ada banyak bilangan prima yang tak terhingga?" kita bisa menjawab "3 + 3 = 6", tetapi ini jelas tidak akan berhasil. Untuk alasan yang sama "false" bukan jawaban yang valid untuk "$P = PSPACE$$P = PSPACE$? ". Saya pikir Frege dan Russell berusaha keras untuk mengajari kami pelajaran itu. Oke, sekarang jawabannya.

Mari saya tunjukkan bagaimana mengekspresikan , arah lain mirip, dan kemudian Anda dapat menempatkan mereka bersama-sama dalam hubungannya untuk mendapatkan P S P A C E = P . Dalam kasus apa pun, untuk keperluan Anda mungkin cukup untuk mengekspresikan P S P A C E ⊆ P , tergantung pada apa yang Anda lakukan.$PSPACE \subseteq P$$PSPACE = P$$PSPACE \subseteq P$

Dengan menggunakan teknik yang mirip dengan yang ada dalam konstruksi predikat Kleene $T$ , kita dapat membuat rumus kuantifer terikat (yang dengan demikian berada di Σ 0 0 = Π 0 0 ) mengatakan "ketika kita menjalankan mesin yang dikodekan oleh k dan mengikat penggunaan ruangnya ke | n | m , mesin menerima input n ." Di sini | n $accept_{space}(k, m, n)$$\Sigma^0_0 = \Pi^0_0$$k$$|n|^m$$n$$|n|$adalah panjang . Cara informal untuk melihat bahwa formula seperti itu ada adalah ini: mengingat k , m , dan n kita dapat menghitung ikatan rekursif primitif pada berapa banyak waktu dan berapa banyak ruang yang akan kita butuhkan (yaitu, paling banyak | n | m ruang dan paling banyak 2 | n | m waktu). Kami kemudian hanya mencari melalui semua jejak eksekusi yang mungkin ada dalam batas yang dikomputasi - pencarian semacam itu agak tidak efisien, tetapi itu adalah rekursif primitif dan jadi kami dapat mengekspresikannya sebagai rumus yang dibatasi.$n$$k$$m$$n$$|n|^m$$2^{|n|^m}$

Ada rumus yang sama di mana waktu berjalan terikat oleh | n | m .$accept_{time}(k, m, n)$$|n|^m$

Sekarang perhatikan rumusnya: Dikatakan bahwa untuk setiap mesin

$$\forall k, m . \exists k', m' . \forall n . accept_{space}(k,m,n) \Leftrightarrow accept_{time}(k',m', n).$$ $k$yang menggunakan paling banyak ruang ada mesin k ′ yang menggunakan paling banyak | | n | m ′ sehingga kedua mesin menerima persis n yang sama . Dengan kata lain, formula mengatakan P S P A C E ⊆ P . Formula ini adalah Π 0 3 .$|n|^m$$k'$$|n|^{m'}$$n$$PSPACE \subseteq P$$\Pi^0_3$

Kita dapat meningkatkan ini jika kita ingin menyatakan sebagai gantinya kalimat " dalam polytime", yang seharusnya cukup baik untuk sebagian besar aplikasi, karena TQBF adalah PSPACE lengkap dan jadi dalam polytime setara dengan P S P A C E ⊆ P . Biarkan k 0 menjadi (kode) mesin yang mengenali TQBF dalam ruang | n | m 0 . Kemudian " T Q B F ∈ P " dapat dinyatakan sebagai ∃ k ′ , m ′$TQBF$$PSPACE \subseteq P$$k_0$$|n|^{m_0}$$TQBF \in P$ Formula ini hanya Σ 0 2 . Jika saya adalah ahli teori kompleksitas, saya akan tahu apakah mungkin untuk melakukan yang lebih baik lagi (tapi saya ragu).

$$\exists k', m' . \forall n . accept_{space}(k_0, m_0, n) \Leftrightarrow accept_{time}(k', m', n).$$ $\Sigma^0_2$

Andrej telah menjelaskan bahwa dapat ditulis sebagai- Σ 0 2- sense. Izinkan saya menyebutkan bahwa klasifikasi ini optimal dalam arti bahwa jika pernyataan tersebut setara dengan- Π 0 2- kalimat, maka fakta ini tidak relativize. Lebih tepatnya, himpunan firman A sehingga P A = P S P A C E A adalah didefinisikan oleh Σ 0 2 -formula dengan orde kedua variabel bebas $P=\mathit{PSPACE}$$\Sigma^0_2$$\Pi^0_2$$A$$P^A=\mathit{PSPACE}^A$$\Sigma^0_2$$A$, Tetapi tidak didefinisikan oleh -formula. Argumen tersebut diuraikan (untuk P = N P , tetapi berfungsi sama untuk P S P A C E ) dalam komentar di /mathpro/57348 . (Faktanya, seseorang dapat menunjukkan dengan elaborasi gagasan bahwa himpunannya Σ 0 2- lengkap dalam arti yang sesuai.)$\Pi^0_2$$P=\mathit{NP}$$\mathit{PSPACE}$$\Sigma^0_2$

EDIT: Bukti topologis yang diberikan dalam komentar tertaut pendek, tetapi mungkin tampak rumit. Berikut ini adalah argumen pemaksaan langsung.

dapat ditulis sebagai Π 0 2- formula dari bentuk ϕ ( A ) = ∀ $P^A\ne\mathit{PSPACE}^A$$\Pi^0_2$ , di mana θ adalah Δ 0 0 . Asumsikan untuk kontradiksi bahwa P A = P S P A C E A juga setara dengan Π 0 2 -formula ψ ( A ) = ∀ $\phi(A)=\forall x\,\exists y\,\theta(A,x,y)$$\theta$$\Delta^0_0$$P^A=\mathit{PSPACE}^A$$\Pi^0_2$ . Fix nubuat B , C sehingga P B ≠ P S P A C E B dan P C = P S P A C E C .$\psi(A)=\forall x\,\exists z\,\eta(A,x,z)$$B$$C$$P^B\ne\mathit{PSPACE}^B$$P^C=\mathit{PSPACE}^C$

Karena , ada y 0 sedemikian rupa sehingga θ ( B , 0 , y 0 ) . Namun, θ adalah rumus terbatas, maka evaluasi nilai kebenaran θ ( B , 0 , y 0 ) hanya menggunakan bagian terbatas dari oracle. Dengan demikian, ada bagian hingga b 0 dari B sehingga θ ( A , 0 , y 0 ) untuk setiap oracle$\phi(B)$$y_0$$\theta(B,0,y_0)$$\theta$$\theta(B,0,y_0)$$b_0$$B$$\theta(A,0,y_0)$ memperpanjang b 0 .$A$$b_0$

Misalkan menunjukkan oracle yang memanjang b 0 , dan setuju dengan C di mana b 0 tidak ditentukan. Karena P A dan P S P A C E A tidak terpengaruh oleh perubahan yang terbatas dalam oracle, kita memiliki ψ ( C [ b 0 ] ) . Dengan argumen yang sama seperti di atas, ada z 0 dan bagian hingga c 0 dari C [ b 0$C[b_0]$$b_0$$C$$b_0$$P^A$$\mathit{PSPACE}^A$$\psi(C[b_0])$$z_0$$c_0$$C[b_0]$sedemikian rupa sehingga untuk setiap A yang meluas c 0 . Kita dapat mengasumsikan bahwa c 0 meluas b 0 .$\eta(A,0,z_0)$$A$$c_0$$c_0$$b_0$

Melanjutkan dengan cara yang sama, kami membangun urutan angka tak terhingga , z 0 , z 1 , z 2 , ... , dan oracle parsial terbatas b 0 ⊆ c 0 ⊆ b 1 ⊆ c 1 ⊆ b 2 ⊆ ⋯ sedemikian rupa$y_0,y_1,y_2,\dots$$z_0,z_1,z_2,\dots$$b_0\subseteq c_0\subseteq b_1\subseteq c_1\subseteq b_2\subseteq\cdots$

1. untuk setiap oracle A memanjang b n ,$\theta(A,n,y_n)$$A$$b_n$

2. untuk setiap oracle A yang meluas c n .$\eta(A,n,z_n)$$A$$c_n$

Sekarang, misalkan menjadi peramal yang mencakup semua b n dan c n . Kemudian 1 dan 2 menyiratkan bahwa ϕ ( A ) dan ψ ( A ) secara bersamaan berlaku, yang bertentangan dengan asumsi bahwa mereka saling melengkapi.$A$$b_n$$c_n$$\phi(A)$$\psi(A)$