Quais são as consequências de ?

14

Um idioma está em se existir uma máquina de Turing de espaço de log que decida o idioma com uma quantidade de conselhos polinomiais.L/poly

Veja aqui para mais informações: https://en.wikipedia.org/wiki/L/poly

Questão

Quais são as consequências de ?PL/poly

Michael Wehar
fonte
Nota: L / poly também é caracterizada como a classe de idiomas que possuem programas de ramificação de tamanho polinomial.
Michael Wehar
1
Existem consequências interessantes de L = P conhecidas? (Significado Interessante que (a) uma prova não-trivial é necessária e (b) a conseqüência não é simplesmente que P teria tal e tal propriedade que L tem incondicionalmente)
William Hoza
Na minha pergunta, estou aberto a quaisquer consequências que os usuários considerem significativas para eles, mesmo que sejam triviais. Algumas conseqüências potenciais que eu estava pensando sobre estavam se implica talvez P = L ou P / p o l y = L / p o l y ou outra coisa mais fraca relacionado a isso. :)PL/polyP=LP/poly=L/poly
Michael Wehar
1
Justo! é realmente uma conseqüência; veja minha resposta para a prova. P/poly=L/poly
William Hoza
1
@WilliamHoza Além disso, acho que implica D T I M E ( t ( n ) ) N T I M E ( t ( n ) ) para certas funções t (P=LDTIME(t(n))NTIME(t(n)) . Consulte "Sobre separadores, segregadores e tempo versus espaço" para obter mais informações. t(n)
Michael Wehar

Respostas:

9

Uma consequência simples é . Prova: para qualquer idioma A P / poli , existe um idioma B P e uma sequência de strings de aconselhamento de comprimento polinomial y 1 , y 2 , y 3 , … de modo que x AP/poly=L/polyAP/polyBPy1,y2,y3, . Por suposição, existe uma linguagem C L e uma sequência de cadeias de aconselhamento de comprimento polinomial z 1 , z 2 , z 3 , tal que ( x , y ) BxA(x,y|x|)BCLz1,z2,z3, . Isso implica A L / poli ; a sequência de conselhos para x é ( y | x | , z | ( x , y | x | ) | ) .(x,y)B(x,y,z|(x,y)|)CAL/polyx(y|x|,z|(x,y|x|)|)

(Uma versão concisa da prova: PL/polyP/poly(L/poly)/poly=L/poly

William Hoza
fonte
Impressionante! Muito obrigado. Eu realmente gostei disso. :)
Michael Wehar