Masalah keputusan yang tidak diketahui dalam PH tetapi akan di P jika P = NP

Sunting : Seperti yang ditunjukkan Ravi Boppana dengan benar dalam jawabannya dan Scott Aaronson juga menambahkan contoh lain dalam jawabannya , jawaban untuk pertanyaan ini ternyata "ya" dengan cara yang tidak saya harapkan sama sekali. Pertama saya berpikir bahwa mereka tidak menjawab pertanyaan yang ingin saya tanyakan, tetapi setelah beberapa pemikiran, konstruksi ini menjawab setidaknya satu dari pertanyaan yang ingin saya tanyakan, yaitu, “Apakah ada cara untuk membuktikan hasil kondisional 'P = NP ⇒ L ∈P 'tanpa membuktikan hasil tanpa syarat L ∈PH? ”Terima kasih, Ravi dan Scott!

Apakah ada masalah keputusan L sehingga kondisi berikut ini terpenuhi?

• L tidak diketahui berada dalam hierarki polinomial.
• Diketahui bahwa P = NP akan menyiratkan L ∈P.

Contoh buatan sama baiknya dengan contoh alami. Juga, meskipun saya menggunakan huruf " L ," itu bisa menjadi masalah yang menjanjikan alih-alih bahasa jika itu membantu.

Latar Belakang . Jika kita tahu bahwa masalah keputusan L adalah dalam hierarki polinomial, maka kita tahu bahwa “P = NP ⇒ L ∈P.” Maksud dari pertanyaan ini adalah untuk menanyakan apakah yang dipertanyakan berlaku. Jika bahasa L yang memenuhi kedua kondisi di atas ada, maka dapat dianggap sebagai bukti bahwa percakapan gagal.

Pertanyaan itu dimotivasi oleh komentar menarik Joe Fitzsimons atas jawaban saya terhadap pertanyaan Walter Bishop, “ Konsekuensi #P = FP .”

Karena Anda tidak keberatan dengan bahasa buatan, bagaimana mendefinisikan menjadi kosong jika P sama dengan NP dan menjadi Masalah Pemutusan jika P tidak sama dengan NP. Oke, ini sedikit curang, tapi saya pikir Anda harus mengulangi masalahnya untuk menghindari penipuan seperti itu. $L$

Jika contoh buatan benar-benar sebagus yang alami, maka saya memang bisa memberikan contoh seperti itu!

Sunting: Selanjutnya, contoh saya "agak" kurang dari cheat daripada yang disarankan oleh Ravi Boppana (di mana kita menganggap L sebagai bahasa kosong jika P = NP dan masalah penghentian sebaliknya), di mana saya akan mendefinisikan bahasa L dengan memberikan prosedur yang terbatas untuk memutuskan apakah L untuk input apa pun x. Pada titik tidak akan memutuskan apakah x∈L membutuhkan pemecahan pertanyaan matematika "tidak terikat" seperti P vs NP.$x \in$

Tanpa basa-basi: biarkan menjadi enumerasi mesin Turing polytime. Untuk semua n , biarkan M t ( n ) menjadi leksikografis pertama M i yang benar memutuskan 3SAT pada semua masukan dari panjang n atau kurang. Kemudian definisikan bahasa L sebagai berikut: untuk semua input x ukuran n , x ∈ L jika dan hanya jika mesin Turing yang dikodekan oleh x berhenti paling banyak n t ( n $M_1, M_2, ...$$n$$M_{t(n)}$$M_i$$n$$x$$n$$x \in$$x$$n^{t(n)}$ langkah saat dijalankan pada kaset kosong.

Klaim 1: Jika P = NP, maka L P.$\in$

Bukti: Jika P = NP, maka ada beberapa tetap yang memecahkan 3SAT untuk semua input; karenanya t ( n ) ≤ $M_i$$t(n) \le i$ untuk semua . QED$n$

Klaim 2: Jika P $\ne$ NP, maka L P.$\notin$

Bukti: Jika bertambah tanpa terikat, maka kita cukup menerapkan Teorema Hirarki Waktu. QED$t(n)$

Sekarang, tidak hanya L tidak dalam P dengan asumsi P NP: orang mengira itu juga tidak ada di PH (atau bahkan PSPACE)!$\ne$

Kebetulan, saya bertanya-tanya apakah ada yang bisa memperbaiki konstruksi di atas, untuk mendapatkan bahasa L yang ada di P jika P = NP, tetapi terbukti tidak di PH atau PSPACE jika P NP?$\ne$

Menjawab pertanyaan Scott Aaronson, tapi agak terlalu lama untuk berkomentar, ini adalah konstruksi bahasa sedemikian rupa sehingga P = N P menyiratkan L ∈ P , tetapi P ≠ N P menyiratkan L ∉ P $L$$P = NP$$L \in P$$P \neq NP$$L \notin PH$ .

Biarkan dan t ( n ) menjadi seperti dalam konstruksi Scott. Kami membuatnya sehingga L tidak mengurangi menjadi Σ k S A T untuk setiap k , tetapi kami hanya melakukan ini jika t ( n ) → ∞ (yaitu jika P ≠ N P ). Pembangunan berlangsung bertahap. Pada tahap s = ( i , $M_1, M_2, M_3, \dotsc$$t(n)$$L$$\Sigma_{k} SAT$$k$$t(n) \to \infty$$P \neq NP$$s=(i,j)$ (menggunakan beberapa penambangan yang mudah dihitung dan mudah dibalik ), kami memastikan bahwa M i bukan pengurangan banyak-banyak dari L ke$\Sigma^* \to \Sigma^* \times \Sigma^*$$M_i$$L$ . Misalkan n s bilangan bulat terkecil sehingga t ( n s ) > t ( n s - 1 ) (kasus dasar: n 0 = 1 ). Jika ada bilangan bulat seperti n s , kemudian mengatur$\Sigma_{j} SAT$$n_{s}$$t(n_{s}) > t(n_{s-1})$$n_{0} = 1$$n_{s}$menjadi kosong selamanya setelah. . Jika tidak ada bilangan bulat seperti n s , kita membiarkan$L(1^{n_{s}}) = 1 - \Sigma_{k}SAT(M_{i}(1^{n_{s}}))$$n_{s}$$L$

Jika , maka t ( $P \neq NP$ sebagai n → ∞ , sehingga selalu ada seperti n s , maka L tidak dalam P H . Jika P = N P , maka saya L hanya finitely berbeda dari Scott L , dan karenanya di P .$t(n) \to \infty$$n \to \infty$$n_{s}$$L$$PH$$P = NP$$L$$L$$P$