| rdfs:comment
| - In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly. In 1979, Aleliunas et al. showed that symmetric logspace is contained in L/poly. However, this result was superseded by Omer Reingold's result that SL collapses to uniform logspace. BPL is contained in L/poly, which is a variant of Adleman's theorem. (en)
- 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 . 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. (pt)
|
| has abstract
| - In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly. Formally, for a formal language L to belong to L/poly, there must exist an advice function f that maps an integer n to a string of length polynomial in n, and a Turing machine M with two read-only input tapes and one read-write tape of size logarithmic in the input size, such that an input x of length n belongs to L if and only if machine M accepts the input x, f(n). Alternatively and more simply, L is in L/poly if and only if it can be recognized by branching programs of polynomial size. One direction of the proof that these two models of computation are equivalent in power is the observation that, if a branching program of polynomial size exists, it can be specified by the advice function and simulated by the Turing machine. In the other direction, a Turing machine with logarithmic writable space and a polynomial advice tape may be simulated by a branching program the states of which represent the combination of the configuration of the writable tape and the position of the Turing machine heads on the other two tapes. In 1979, Aleliunas et al. showed that symmetric logspace is contained in L/poly. However, this result was superseded by Omer Reingold's result that SL collapses to uniform logspace. BPL is contained in L/poly, which is a variant of Adleman's theorem. (en)
- 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 . 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). 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. 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. (pt)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)