Kompleksitas Zoo menunjukkan dalam entri pada EXP bahwa jika L = P maka PSPACE = EXP. Karena NPSPACE = PSPACE oleh Savitch, sejauh yang saya tahu argumen padding yang mendasarinya meluas untuk menunjukkan bahwa Kita juga tahu bahwa L NL NC P via hirarki bergantian sumber daya Ruzzo.
Jika NC = P, apakah ini mengikuti PSPACE = EXP?
Penafsiran yang berbeda dari pertanyaan, dalam semangat Richard Lipton: apakah lebih mungkin bahwa beberapa masalah dalam P tidak dapat diparalelkan, daripada bahwa tidak ada prosedur waktu eksponensial yang membutuhkan lebih dari ruang polinomial?
Saya juga akan tertarik pada konsekuensi "mengejutkan" lainnya dari NC = P (semakin tidak mungkin semakin baik).
Sunting: Jawaban Ryan mengarah ke pertanyaan lebih lanjut: apa hipotesis terlemah yang diketahui menjamin PSPACE = EXP?
- W. Savitch. Hubungan antara kompleksitas pita nondeterministik dan deterministik, Jurnal Ilmu Komputer dan Sistem 4 (2): 177-192, 1970.
- WL Ruzzo. Pada kompleksitas sirkuit yang seragam, Jurnal Ilmu Komputer dan Sistem 22 (3): 365-383, 1971.
Edit (2014): tautan Kebun Binatang lama yang diperbarui dan tautan yang ditambahkan untuk semua kelas lainnya.
sumber
Jawaban:
Iya nih. dapat dilihat sebagai kelas bahasa yang dikenali oleh mesin Turing bergantian yang menggunakan ruang dan waktu. (Ini pertama kali dibuktikan oleh Ruzzo.) adalah kelas di mana mesin Turing bergantian menggunakan ruang tetapi bisa memakan waktu hingga waktu. Untuk singkatnya sebut kelas ini dan .O ( log n ) ( log n ) O ( 1 ) P O ( log n ) n O ( 1 ) A T I S P [ ( log n ) O ( 1 ) , log n ] = N C A S P A C E [ O ( log n ) ]NC O ( logn ) ( logn )O ( 1 ) P O ( logn ) nO ( 1 ) A TsayaSP[ ( logn )O ( 1 ), logn ] = NC A SPA CE[ O ( logn ) ] = P
Misalkan kedua kelas itu sama. Mengganti dengan 2 n di atas (yaitu, menerapkan lemma terjemahan standar), orang memperolehn 2n
.TsayaM.E[ 2O ( n )] = A SPA CE[ O ( n ) ] = A TsayaSP[ nO ( 1 ), n ] ⊆ A TsayaM.E[ nO ( 1 )] = PSPA CE
Jika maka E X P = P S P A C E juga, karena ada E X P- bahasa lengkap di T I M E [ 2 O ( n ) ] .TsayaM.E[ 2O ( n )] ⊆ PSPA CE EXP= PSPA CE EXP TsayaM.E[ 2O ( n )]
Sunting: Meskipun jawaban di atas mungkin lebih bersifat mendidik, berikut argumen yang lebih sederhana: sudah mengikuti dari " P dimuat dalam ruang polylog" dan terjemahan standar.EXP= PSPA CE P Catatan " yang terkandung dalam ruang polylog" adalah hipotesis jauh lebih lemah daripada N C = P .P NC= P
Lebih detail: Sejak keluarga sirkuit memiliki kedalaman ( log n ) c untuk beberapa konstan, setiap keluarga sirkuit tersebut dapat dievaluasi dalam O ( ( log n ) c ) ruang. Oleh karena itu N C ⊆ ⋃ c > 0 S P A C E [ ( log n ) c ] . Jadi P = N C menyiratkan P ⊆ ⋃ c > 0 SNC ( logn )c O ( ( logn )c) NC⊆ ⋃c > 0SPA CE[ ( logn )c] P= NC . Menerapkan terjemahan (menggantikan n dengan 2 n ) menyiratkan T I M E [ 2 O ( n ) ] ⊆ P S P A C E . Keberadaanbahasa lengkap E X P dalam T I M E [ 2 O ( n ) ] menyelesaikan argumen.P⊆ ⋃c > 0SPA CE[ ( logn )c] n 2n TsayaM.E[ 2O ( n )] ⊆ PSPA CE EXP TsayaM.E[ 2O ( n )]
Pembaruan: Mengatasi pertanyaan tambahan Andreas, saya percaya seharusnya bisa membuktikan sesuatu seperti: iff untuk semua c , setiap bahasa jarang secara polinomi dalam n O ( log c n ) waktu dapat dipecahkan dalam ruang polylog. (Jarang secara polinomi berarti bahwa ada paling banyak p o l y ( n ) string panjang n dalam bahasa, untuk semua nEXP= PSPA CE c nO ( logcn ) p o l y( n ) n n .) Jika benar, buktinya mungkin akan pergi sepanjang garis Hartmanis, Immerman, dan bukti Sewelson yang IFF setiap bahasa polynomially jarang di N P terkandung dalam P . (Catatan, n O ( log c n ) waktu dalam ruang polylog masih cukup untuk menyiratkan P S P A C E = E X P. )NE= E NP P nO ( logcn ) PSPA CE= EXP
sumber
(Saya sudah melihat jawaban Ryan, tetapi saya hanya ingin memberikan perspektif lain, yang terlalu panjang untuk dimasukkan ke dalam komentar.)
Dalam bukti, semua yang perlu Anda ketahui tentang L, secara informal, adalah bahwa ketika diledakkan oleh eksponensial, L menjadi PSPACE. Bukti yang sama berlaku untuk NL, karena NL yang meledak oleh eksponensial juga menjadi PSPACE.L = P⇒ P.SPA CE= EXP
Demikian pula, ketika NC diledakkan oleh eksponensial, Anda mendapatkan PSPACE. Saya suka melihat ini dalam hal sirkuit: NC adalah kelas sirkuit ukuran polinom dengan kedalaman polylog. Ketika diledakkan, ini menjadi sirkuit ukuran eksponensial dengan kedalaman polinomial. Orang dapat menunjukkan bahwa ini persis PSPACE, setelah kondisi keseragaman yang sesuai ditambahkan. Saya kira jika NC didefinisikan dengan L-uniformity, maka ini akan mendapatkan PSPACE-uniformity.
Buktinya harus mudah. Dalam satu arah, ambil masalah lengkap PSPACE seperti TQBF dan ekspresikan pengukur menggunakan gerbang AND dan OR dengan ukuran eksponensial. Di arah lain, coba lintasi sirkuit kedalaman polinomial secara rekursif. Ukuran tumpukan akan polinomial, jadi ini bisa dilakukan di PSPACE.
Akhirnya, saya muncul dengan argumen ini ketika saya melihat pertanyaan (dan sebelum membaca jawaban Ryan), jadi mungkin ada bug. Tolong tunjukkan.
sumber
Berikut ini sedikit lebih detail dari perspektif simulasi ruang-waktu yang dibatasi mesin Alternating Turing.
Misalkan .P= NC
Karena , kita mendapatkan P = A T I S P ( ( log ( n ) ) O ( 1 ) , O ( log ( n ) ) ) .NC= A TsayaSP( ( log( n ) )O ( 1 ), O ( log( n ) ) )
Sekarang, pertimbangkan masalah simulasi universal waktu linear mana kita diberikan pengkodean pada mesin Turing M dan string input x panjang n dan kami ingin tahu apakah M menerima x paling banyak dalam n langkah.L i n U M. x n M. x n
Kita tahu bahwa . Oleh karena itu, ada konstanta c (cukup besar) sehingga ( ∗ )L i n U∈ P. c
Sebagai hasil dari argumen padding (sedikit rumit melihat komentar), kami memiliki
Memperluas argumen padding, kita dapatkan ( 3 )
Selanjutnya, ada hasil yang diketahui tentang simulasi mesin Turing yang dibatasi ruang-waktu. Secara khusus, kita tahu bahwa
Oleh karena itu, kami (pada dasarnya) memiliki yang berikut untuk semua bilangan asli :k
( 3 ∗ )
Dari , kita akan mendapatkan bahwa E X P = P S P A C E .( 3)∗) EXP= PSPA CE
==================== Setelah Pikir ===================
Penting untuk memperhatikan bahwa menyiratkan A T I S P ( ( log ( n ) ) O ( 1 ) , O ( log ( n ) ) ) = A T I S P ( log c ( n ) , O ( log ( n ) ) ) untuk beberapa konstanta c .P= NC
Setiap komentar atau koreksi disambut. :)
sumber