| dbo:abstract
|
- En informatique théorique, plus précisément en théorie de la complexité, le théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est le théorème qui énonce que la classe probabiliste BPP (bounded-error probabilistic polynomial time) est incluse dans la hiérarchie polynomiale. Cette relation d'inclusion est surprenante[Selon qui ?] car la définition de la hiérarchie polynomiale ne fait pas référence à la théorie des probabilités. (fr)
- In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2. In 1983, Michael Sipser showed that BPP is contained in the polynomial time hierarchy. showed that BPP is actually contained in Σ2 ∩ Π2. contributed by giving a simple proof of BPP’s membership in Σ2 ∩ Π2, also in 1983. It is conjectured that in fact BPP=P, which is a much stronger statement than the Sipser–Lautemann theorem. (en)
- Em teoria da complexidade computacional, o teorema Sipser-Lautemann ou teorema Sipser-Gács-Lautemann estabelece que Bounded-error probabilistic polinomial time (BPP), está contida na hierarquia de tempo polinomial, e, mais especificamente, em Σ2 ∩ Π2. Em 1983, Michael Sipser mostrou que BPP está contida na hierarquia de tempo polinomial. mostrou que BPP está atualmente inserida em Σ2 ∩ Π2. contribuiu dando uma prova simples de que BPP está contida em Σ2 ∩ Π2, também em 1983. Conjectura-se que, na realidade, BPP = P, que é uma afirmação mais forte do que o teorema de Sipser-Lautemann. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6261 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:b
| |
| dbp:p
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En informatique théorique, plus précisément en théorie de la complexité, le théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est le théorème qui énonce que la classe probabiliste BPP (bounded-error probabilistic polynomial time) est incluse dans la hiérarchie polynomiale. Cette relation d'inclusion est surprenante[Selon qui ?] car la définition de la hiérarchie polynomiale ne fait pas référence à la théorie des probabilités. (fr)
- In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2. In 1983, Michael Sipser showed that BPP is contained in the polynomial time hierarchy. showed that BPP is actually contained in Σ2 ∩ Π2. contributed by giving a simple proof of BPP’s membership in Σ2 ∩ Π2, also in 1983. It is conjectured that in fact BPP=P, which is a much stronger statement than the Sipser–Lautemann theorem. (en)
- Em teoria da complexidade computacional, o teorema Sipser-Lautemann ou teorema Sipser-Gács-Lautemann estabelece que Bounded-error probabilistic polinomial time (BPP), está contida na hierarquia de tempo polinomial, e, mais especificamente, em Σ2 ∩ Π2. Em 1983, Michael Sipser mostrou que BPP está contida na hierarquia de tempo polinomial. mostrou que BPP está atualmente inserida em Σ2 ∩ Π2. contribuiu dando uma prova simples de que BPP está contida em Σ2 ∩ Π2, também em 1983. Conjectura-se que, na realidade, BPP = P, que é uma afirmação mais forte do que o teorema de Sipser-Lautemann. (pt)
|
| rdfs:label
|
- Théorème de Sipser-Gács-Lautemann (fr)
- Teorema de Sipser–Lautemann (pt)
- Sipser–Lautemann theorem (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
