Na teoria da complexidade computacional, L/poly é a classe de máquinas de espaço logarítmico com uma quantidade polinomial de palavras de aviso. L/poly é uma classe de espaço logaritmica não uniforme, análogo ao não uniformismo de tempo polinomial da classe P/poly.Complexity Zoo: L/poly
Formalmente, para uma linguagem formal L pertencer a L/poly, deve existir uma função certificado que mapeia um inteiro para uma string cujo tamanho é um polinômio em função de , e uma máquina de Turing M com duas fitas somente de leitura e uma de leitura-escrita cujos tamanhos são uma função logaritmica do tamanho da entrada, tal que a entrada de tamanho pertença a se, e somente se, a máquina M aceita a entrada . Alternativamente e mais simples, está em L/poly se, e somente se, ela pode ser reconhecida por um programa de ramificação de tamanho polinomial. Uma direção da prova que esses dois modelos de computação são equivalentes em poder está na observação que: se o programa de ramificação de tamanho polinomial existe, ele pode ser especificado por uma função certificado e simulada por uma máquina de Turing. Na outra direção, uma máquina de Turing com um espaço de escrita logaritmico e um espaço de leitura polinomial pode ser simulado por um programa de ramificação cujos estados representam a combinação das configurações da fita que pode ser escrita e da posição do cabeçote da máquina de Turing nas outras duas fitas.
Em 1979, Aleliunas et al. mostrou que logspace simétrica está contida em L/poly. Entretanto, este resultado foi superado pelo resultado de que SL colapsa sobre uma logspace uniforme, de Omer Reingold.
BPL está contido em L/poly, que é uma variante do teorema de Adleman..
Categoria:Computação