Apa konsekuensi dari ?

14

Sebuah bahasa dalam L./halHaily jika ada mesin Turing logspace yang memutuskan bahasa dengan jumlah saran polinomial.

Lihat di sini untuk info lebih lanjut: https://en.wikipedia.org/wiki/L/poly

Pertanyaan

Apa konsekuensi dari ?PL./halHaily

Michael Wehar
sumber
Catatan: L / poli juga ditandai sebagai kelas bahasa yang memiliki program percabangan ukuran polinomial.
Michael Wehar
1
Adakah konsekuensi menarik dari L = P yang diketahui? (Arti yang menarik bahwa (a) bukti nontrivial diperlukan dan (b) konsekuensinya bukan hanya bahwa P akan memiliki properti ini-dan-seperti yang dimiliki L tanpa syarat)
William Hoza
Dalam pertanyaan saya, saya terbuka terhadap konsekuensi apa pun yang pengguna anggap bermakna bagi mereka meskipun mereka sepele. Seorang calon beberapa konsekuensi yang saya bertanya-tanya tentang itu jika menyiratkan mungkin P = L atau P / p o l y = L / p o l y atau sesuatu yang lain yang lebih lemah yang berkaitan dengan ini. :)PL./halHailyP=L.P/halHaily=L./halHaily
Michael Wehar
1
Cukup adil! memang merupakan konsekuensi; lihat jawaban saya untuk buktinya. P/halHaily=L./halHaily
William Hoza
1
@ WilliamHoza Juga, saya pikir menyiratkan D T I M E ( t ( n ) ) N T I M E ( t ( n ) ) untuk fungsi-fungsi tertentu t ( n ) . Lihat "Pemisah, Segregator, dan Waktu versus Ruang" untuk info lebih lanjut. P=L.DTsayaM.E(t(n))NTsayaM.E(t(n))t(n)
Michael Wehar

Jawaban:

9

Salah satu konsekuensi sederhana adalah . Bukti: Untuk bahasa apa pun A P / poli , ada bahasa B P dan urutan string saran panjang polinomial y 1 , y 2 , y 3 , sedemikian rupa sehingga x AP/poli=L./poliSEBUAHP/poliBPy1,y2,y3,... . Dengan asumsi, ada bahasa C L dan urutan string panjang polinomial saran z 1 , z 2 , z 3 , sedemikian rupa sehingga ( x , y ) BxA(x,y|x|)BCL.z1,z2,z3,... . Ini menyiratkan A L / poli ; string saran untuk x adalah ( y | x | , z | ( x , y | x | ) | ) .(x,y)B(x,y,z|(x,y)|)CSEBUAHL./polix(y|x|,z|(x,y|x|)|)

(Versi singkat dari buktinya: .)PL/polyP/poly(L/poly)/poly=L/poly

William Hoza
sumber
Luar biasa! Terima kasih banyak. Saya sangat menghargai itu. :)
Michael Wehar