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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Théorème de Sipser-Gács-Lautemann (fr)
- Teorema de Sipser–Lautemann (pt)
- Sipser–Lautemann theorem (en)
|
| 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)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| b
| |
| p
| |
| has 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)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
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)