In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - BPL (complexity) (en)
- BPL (complexidade) (pt)
- BPL (複雜度) (zh)
|
| rdfs:comment
| - In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction. (en)
- Na teoria da complexidade computacional, BPL (Bounded-error Probabilistic Logarithmic-space, i.e. Espaço Logarítmico Probabilístico de Erro Limitado), às vezes chamada de BPLP (Espaço Logarítmico Probabilístico de Erro Limitado e Tempo Polinomial), é a classe de complexidade dos problemas solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro bilateral. É assim denominado, em analogia com o BPP, que é semelhante, mas não tem restrição de espaço logarítmico. BPL está contida em NC e em DSPACE(log3/2 n) e em L/poly. (pt)
- 在計算複雜度理論領域內，BPL（有限錯誤機率對數空間，Bounded-error Probabilistic Logarithmic-space）或者叫做BPLP（有限錯誤機率對數空間多項式時間，Bounded-error Probabilistic Logarithmic-space Polynomial-time）是一個使用機率圖靈機可以在多項式時間時間以及對數空間解決的問題，但是有雙邊錯誤（two-sided error）。這個類別的名稱類似BPP，一個很接近但是沒有對數空間限制的類別。 BPL裡面的機率圖靈機會在回答接收或者拒絕的時候，犯下機率小於1/3的錯誤；這個被稱呼為雙邊錯誤。 這裡1/3的常數是一個抽象的概念：任何0 ≤ x < 1/2都可以滿足這個定義。藉由重複整個演算法，我們可以限縮誤差機率小於2−p(x)（這裡的p(x)為任意多項式），並且不使用多項式時間和對數空間以上的資源。 雖然雙邊錯誤比起單邊錯誤（回答特定答案時絕不會出錯，只有在另一個答案時會）更加一般化，RL和它的co-RL包含在BPL裡面。BPL也包含在（一個相類似的複雜度類，不過其錯誤率恰為1/2而非小於1/2）裡面；就像PP一樣，PL可能需要花費很多次的計算來降低錯誤的機率，因此比較不實用。 (zh)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction. (en)
- Na teoria da complexidade computacional, BPL (Bounded-error Probabilistic Logarithmic-space, i.e. Espaço Logarítmico Probabilístico de Erro Limitado), às vezes chamada de BPLP (Espaço Logarítmico Probabilístico de Erro Limitado e Tempo Polinomial), é a classe de complexidade dos problemas solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro bilateral. É assim denominado, em analogia com o BPP, que é semelhante, mas não tem restrição de espaço logarítmico. As máquinas de Turing probabilísticas na definição de BPL podem apenas aceitar ou rejeitar incorretamente menos de 1/3 das vezes; isto é chamado de erro bilateral. A constante de 1/3 é arbitrária; qualquer x , com 0 ≤ x < 1/2 seria suficiente. Este erro pode ser reduzido em 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. Já que erro bilateral é mais geral que o erro unilateral, RL e seu complemento co-RL estão contidos em BPL, BPL também está em PL, o que é similar, exceto que o limite do erro é 1/2 ao invés de uma constante a menos que 1/2; assim como a classe PP, a classe PL é menos prática pois pode precisar de uma grande quantidade de iterações para reduzir a probabilidade de erro a uma pequena constante. mostrou o resultado fraco da desrandomização de que BPL está contida em SC. SC é a classe de problemas solúveis em tempo polinomial e espaço logarítmico numa máquina de Turing determinística; em outras palavras, este resultado mostra que dado um espaço polilogaritmico, uma máquina determinística consegue simular algoritmos probabilísticos de espaço logarítmico. BPL está contida em NC e em DSPACE(log3/2 n) e em L/poly. (pt)
- 在計算複雜度理論領域內，BPL（有限錯誤機率對數空間，Bounded-error Probabilistic Logarithmic-space）或者叫做BPLP（有限錯誤機率對數空間多項式時間，Bounded-error Probabilistic Logarithmic-space Polynomial-time）是一個使用機率圖靈機可以在多項式時間時間以及對數空間解決的問題，但是有雙邊錯誤（two-sided error）。這個類別的名稱類似BPP，一個很接近但是沒有對數空間限制的類別。 BPL裡面的機率圖靈機會在回答接收或者拒絕的時候，犯下機率小於1/3的錯誤；這個被稱呼為雙邊錯誤。 這裡1/3的常數是一個抽象的概念：任何0 ≤ x < 1/2都可以滿足這個定義。藉由重複整個演算法，我們可以限縮誤差機率小於2−p(x)（這裡的p(x)為任意多項式），並且不使用多項式時間和對數空間以上的資源。 雖然雙邊錯誤比起單邊錯誤（回答特定答案時絕不會出錯，只有在另一個答案時會）更加一般化，RL和它的co-RL包含在BPL裡面。BPL也包含在（一個相類似的複雜度類，不過其錯誤率恰為1/2而非小於1/2）裡面；就像PP一樣，PL可能需要花費很多次的計算來降低錯誤的機率，因此比較不實用。 )使用了一個弱的去隨機化結果證明BPL包含在SC裡面。這裡的SC是一個複雜度類，包含可以使用決定型圖靈機在多項式時間和多項式對數（polylogarithmic）空間解決的問題；換句話說，這個結論證明了給予多項式對數空間，一個決定型機器可以模擬對數空間的機率演算法。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[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)