L/Poly
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.[1]
Formalmente, para uma linguagem formal L pertencer a L/poly, deve existir uma função certificado f que mapeia um inteiro n para uma string cujo tamanho é um polinômio em função de n, 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 x de tamanho n pertença a L se, e somente se, a máquina M aceita a entrada x, f(n).[2] Alternativamente e mais simples, L está em L/poly se, e somente se, ela pode ser reconhecida por um programa de ramificação de tamanho polinomial.[3] 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.[4] Entretanto, este resultado foi superado pelo resultado de que SL colapsa sobre uma logspace uniforme, de Omer Reingold.[5]
BPL está contido em L/poly, que é uma variante do teorema de Adleman.[6]
Referências
- ↑ Complexity Zoo: L/poly
- ↑ Thierauf, Thomas (2000), The Computational Complexity of Equivalence and Isomorphism Problems, ISBN 978-3-540-41032-4, Lecture Notes in Computer Science, 1852, Springer-Verlag, p. 66
- ↑ Cobham, Alan (1966), «The recognition problem for the set of perfect squares», Proceedings of the 7th Annual IEEE Symposium on Switching and Automata Theory (SWAT 1966), pp. 78–87, doi:10.1109/SWAT.1966.30
- ↑ Aleliunas, Romas; Karp, Richard M.; Lipton, Richard J.; Lovász, László; Rackoff, Charles (1979), «Random walks, universal traversal sequences, and the complexity of maze problems», Proceedings of 20th Annual Symposium on Foundations of Computer Science, New York: IEEE, pp. 218–223, MR 598110, doi:10.1109/SFCS.1979.34
- ↑ Reingold, Omer (2008), «Undirected connectivity in log-space», Journal of the ACM, 55 (4): 1–24, MR 2445014, doi:10.1145/1391289.1391291
- ↑ Nisan, Noam (1993), «On read-once vs. multiple access to randomness in logspace», Theoretical Computer Science, 107 (1): 135–144, MR 1201169, doi:10.1016/0304-3975(93)90258-U.