Język jest w języku jeśli istnieje maszyna Turinga z logami, która decyduje o języku z wielomianową ilością porad.
Zobacz tutaj, aby uzyskać więcej informacji: https://en.wikipedia.org/wiki/L/poly
Pytanie
Jakie są konsekwencje ?
cc.complexity-theory
circuit-complexity
polynomial-time
advice-and-nonuniformity
logspace
Michael Wehar
źródło
źródło
Odpowiedzi:
Jedną z prostych konsekwencji jest . Dowód: dla dowolnego języka A ∈ P / poli istnieje język B ∈ P i sekwencja ciągów porad wielomianowych y 1 , y 2 , y 3 , … takich, że x ∈ AP/poly=L/poly A∈P/poly B∈P y1,y2,y3,… . Z założenia istnieje język C ∈ L i sekwencja ciągów porad wielomianowych z 1 , z 2 , z 3 , … takich, że ( x , y ) ∈ Bx∈A⟺(x,y|x|)∈B C∈L z1,z2,z3,… . To implikuje A ∈ L / poli ; ciąg porady dla x to ( y | x | , z | ( x , y | x | ) | ) .(x,y)∈B⟺(x,y,z|(x,y)|)∈C A∈L/poly x (y|x|,z|(x,y|x|)|)
(Zwięzła wersja dowodu:P⊆L/poly⟹P/poly⊆(L/poly)/poly=L/poly
źródło