L/Poly: diferenças entre revisões
Wikilinks, wiki markup, spelling. (ftr, estou a fazer isto em comparação com a revisão 535473797 da enwiki) |
Converter referência para wikimarkup (código wiki da referência copiado de 535473797 da enwiki, o que resulta precisamente no mesmo texto que já estava no artigo) |
||
| Linha 1: | Linha 1: | ||
Na [[teoria da complexidade computacional]], '''L/poly''' é a classe de máquinas de [[LSPACE|espaço logarítmico]] com uma quantidade polinomial de [[palavra de aviso|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]].<ref>Complexity Zoo: L/poly</ref> |
Na [[teoria da complexidade computacional]], '''L/poly''' é a classe de máquinas de [[LSPACE|espaço logarítmico]] com uma quantidade polinomial de [[palavra de aviso|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]].<ref>Complexity Zoo: L/poly</ref> |
||
Formalmente, para uma [[linguagem formal]] L pertencer a L/poly, deve existir uma função certificado {{mvar|f}} que mapeia um inteiro {{mvar|n}} para uma string cujo tamanho é um polinômio em função de {{mvar|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 {{mvar|x}} de tamanho {{mvar|n}} pertença a {{mvar|L}} se, e somente se, a máquina M aceita a entrada {{math|''x'', ''f''(''n'')}}. |
Formalmente, para uma [[linguagem formal]] L pertencer a L/poly, deve existir uma função certificado {{mvar|f}} que mapeia um inteiro {{mvar|n}} para uma string cujo tamanho é um polinômio em função de {{mvar|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 {{mvar|x}} de tamanho {{mvar|n}} pertença a {{mvar|L}} se, e somente se, a máquina M aceita a entrada {{math|''x'', ''f''(''n'')}}.<ref>{{citation|title=The Computational Complexity of Equivalence and Isomorphism Problems|volume=1852|series=Lecture Notes in Computer Science|first=Thomas|last=Thierauf|publisher=Springer-Verlag|year=2000|isbn=978-3-540-41032-4|page=66|url=http://books.google.com/books?id=e3xOiREJF4EC&pg=PA66}}</ref> 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 podes er escrita e da posição o cabeçote da máquina de Turing nas outras duas fitas. |
||
Em 1979, Aleliunas et al. mostrou que uma logscape simétrica está contida em L/poly.[4] Entretanto, este resultado foi superado pelo resultado de que SL colapsa sobre uma logscape uniforme, de Omer Reingold.[5] |
Em 1979, Aleliunas et al. mostrou que uma logscape simétrica está contida em L/poly.[4] Entretanto, este resultado foi superado pelo resultado de que SL colapsa sobre uma logscape uniforme, de Omer Reingold.[5] |
||
| Linha 8: | Linha 8: | ||
{{referências}} |
{{referências}} |
||
^ Thierauf, Thomas (2000), The Computational Complexity of Equivalence and Isomorphism Problems, Lecture Notes in Computer Science 1852, Springer-Verlag, p. 66, ISBN 978-3-540-41032-4. |
|||
^ 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. |
^ 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, doi:10.1109/SFCS.1979.34, MR 598110. |
^ 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, doi:10.1109/SFCS.1979.34, MR 598110. |
||
Revisão das 08h45min de 21 de dezembro de 2022
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 podes er escrita e da posição o cabeçote da máquina de Turing nas outras duas fitas.
Em 1979, Aleliunas et al. mostrou que uma logscape simétrica está contida em L/poly.[4] Entretanto, este resultado foi superado pelo resultado de que SL colapsa sobre uma logscape uniforme, de Omer Reingold.[5]
BPL está contido em L/poly, que é uma variante do teorema de Adleman's.[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, doi:10.1109/SFCS.1979.34, MR 598110. ^ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM 55 (4): 1–24, doi:10.1145/1391289.1391291, MR 2445014. ^ Nisan, Noam (1993), "On read-once vs. multiple access to randomness in logspace", Theoretical Computer Science 107 (1): 135–144, doi:10.1016/0304-3975(93)90258-U, MR 1201169.