Sebuah bahasa dalam 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 ?
cc.complexity-theory
circuit-complexity
polynomial-time
advice-and-nonuniformity
logspace
Michael Wehar
sumber
sumber
Jawaban:
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 / poli A ∈ P / poli B ∈ P y1, 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 ) ∈ Bx ∈ A⟺(x,y|x|)∈B C∈L 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) |) ∈ C A ∈ L / poli x ( y| x |, z| (x, y| x |) |)
(Versi singkat dari buktinya: .)P⊆L/poly⟹P/poly⊆(L/poly)/poly=L/poly
sumber