| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat RL (també coneguda per RLP) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en espai logarítmic i temps polinòmic. És anàloga a la classe RP, que no té la restricció d'espai logarítmic. La màquina de Turing probabilística de la definició mai accepta incorrectament una entrada, però pot rebutjar incorrectament amb una probabilitat menor de 1/3 (aquesta característica s'anomena error d'una banda (one side error)). La constant 1/3 és arbitrària, qualsevol valor entre 0 i 1 és vàlid. (ca)
- In der Komplexitätstheorie ist RL die Klasse der Entscheidungsprobleme, die von einer probabilistischen Turingmaschine auf logarithmischen Platz mit beschränkter einseitiger Irrtumswahrscheinlichkeit lösbar sind. (de)
- Randomized Logarithmic-space (RL), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction. (en)
- Espaço Logarítmico Randomizado (RL), às vezes chamado de RLP (Espaço Logarítmico Randomizado de tempo Polinomial), é a classe de complexidade de problemas da teoria da complexidade computacional solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro unilateral. É denominado analogamente a RP, que é semelhante, mas não tem restrição logarítmica de espaço. As máquinas de Turing probabilísticas na definição de RL nunca aceitam incorretamente, mas são permitidas de rejeitar incorretamente menos de 1/3 das vezes; isso é chamado de erro unilateral. A constante 1/3 é arbitrária; qualquer x , com 0 < x < 1 seria o suficiente. Este erro pode reduzido 2−p(x) vezes para qualquer polinômio p(x) sem utilizar mais do que um tempo polinomial ou espaço logarítmico ao se executar o algoritmo várias vezes. Às vezes, o nome RL é reservado para a classe de problemas solúveis por máquinas probabilísticas de espaço logarítmico em tempo infinito. No entanto, esta classe pode ser demonstrada como sendo igual a NL utilizando um contador probabilístico, e por isso é geralmente referida como NL em vez disso, o que também mostra que RL está contida em NL. RL está contida em BPL, que é semelhante, mas permite erro bilateral (aceitações incorretas). RL contém L, problemas solúveis por máquinas de Turing determinísticas em espaço logarítmico, já que sua definição é apenas mais geral. Noam Nisan mostrou, em 1992, o resultado fraco de derandomização fraca de que RL está contida em SC, a classe de problemas solúveis em tempo polinomial e espaço polilogarítmico numa máquina de Turing determinística; em outras palavras, dado um espaço polilogarítmico, um máquina determinística pode simular algoritmos probabilísticos em espaço logarítmico. Acredita-se que RL é igual a L, isto é, que computação de tempo polinomial logspace (espaço logarítmico) pode ser completamente desrandomizada (não-aleatória); as principais evidências para isso foram apresentadas por Reingold et al. no ano de 2005. Uma prova disso é o santo graal dos esforços no campo de desrandomização incondicional de classes de complexidade. Um passo importante foi a prova de Omer Reingold de que SL é igual a L. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3203 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat RL (també coneguda per RLP) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en espai logarítmic i temps polinòmic. És anàloga a la classe RP, que no té la restricció d'espai logarítmic. La màquina de Turing probabilística de la definició mai accepta incorrectament una entrada, però pot rebutjar incorrectament amb una probabilitat menor de 1/3 (aquesta característica s'anomena error d'una banda (one side error)). La constant 1/3 és arbitrària, qualsevol valor entre 0 i 1 és vàlid. (ca)
- In der Komplexitätstheorie ist RL die Klasse der Entscheidungsprobleme, die von einer probabilistischen Turingmaschine auf logarithmischen Platz mit beschränkter einseitiger Irrtumswahrscheinlichkeit lösbar sind. (de)
- Randomized Logarithmic-space (RL), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction. (en)
- Espaço Logarítmico Randomizado (RL), às vezes chamado de RLP (Espaço Logarítmico Randomizado de tempo Polinomial), é a classe de complexidade de problemas da teoria da complexidade computacional solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro unilateral. É denominado analogamente a RP, que é semelhante, mas não tem restrição logarítmica de espaço. (pt)
|
| rdfs:label
|
- RL (Complexitat) (ca)
- RL (Komplexitätsklasse) (de)
- RL (complexity) (en)
- RL (complexidade) (pt)
- RL (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |