Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Sipser–Lautemann_theorem> ?p ?o }
Showing triples 1 to 42 of
42
with 100 triples per page.
- Sipser–Lautemann_theorem abstract "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. Péter Gács showed that BPP is actually contained in Σ2 ∩ Π2. Clemens Lautemann 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.".
- Sipser–Lautemann_theorem wikiPageID "2921620".
- Sipser–Lautemann_theorem wikiPageLength "8986".
- Sipser–Lautemann_theorem wikiPageOutDegree "17".
- Sipser–Lautemann_theorem wikiPageRevisionID "684363414".
- Sipser–Lautemann_theorem wikiPageWikiLink Arthur–Merlin_protocol.
- Sipser–Lautemann_theorem wikiPageWikiLink BPP_(complexity).
- Sipser–Lautemann_theorem wikiPageWikiLink Category:Articles_containing_proofs.
- Sipser–Lautemann_theorem wikiPageWikiLink Category:Probabilistic_complexity_theory.
- Sipser–Lautemann_theorem wikiPageWikiLink Category:Structural_complexity_theory.
- Sipser–Lautemann_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
- Sipser–Lautemann_theorem wikiPageWikiLink Clemens_Lautemann.
- Sipser–Lautemann_theorem wikiPageWikiLink Complement_(complexity).
- Sipser–Lautemann_theorem wikiPageWikiLink Computational_complexity_theory.
- Sipser–Lautemann_theorem wikiPageWikiLink Exclusive_or.
- Sipser–Lautemann_theorem wikiPageWikiLink Michael_Sipser.
- Sipser–Lautemann_theorem wikiPageWikiLink P_(complexity).
- Sipser–Lautemann_theorem wikiPageWikiLink Polynomial_hierarchy.
- Sipser–Lautemann_theorem wikiPageWikiLink Péter_Gács.
- Sipser–Lautemann_theorem wikiPageWikiLink S2P_(complexity).
- Sipser–Lautemann_theorem wikiPageWikiLinkText "Sipser–Lautemann theorem".
- Sipser–Lautemann_theorem wikiPageWikiLinkText "Sipser–Lautemann_theorem".
- Sipser–Lautemann_theorem b "2".
- Sipser–Lautemann_theorem p "P".
- Sipser–Lautemann_theorem wikiPageUsesTemplate Template:.
- Sipser–Lautemann_theorem wikiPageUsesTemplate Template:Su.
- Sipser–Lautemann_theorem subject Category:Articles_containing_proofs.
- Sipser–Lautemann_theorem subject Category:Probabilistic_complexity_theory.
- Sipser–Lautemann_theorem subject Category:Structural_complexity_theory.
- Sipser–Lautemann_theorem subject Category:Theorems_in_computational_complexity_theory.
- Sipser–Lautemann_theorem type Proof.
- Sipser–Lautemann_theorem type Redirect.
- Sipser–Lautemann_theorem type Theorem.
- Sipser–Lautemann_theorem comment "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. Péter Gács showed that BPP is actually contained in Σ2 ∩ Π2. Clemens Lautemann contributed by giving a simple proof of BPP’s membership in Σ2 ∩ Π2, also in 1983.".
- Sipser–Lautemann_theorem label "Sipser–Lautemann theorem".
- Sipser–Lautemann_theorem sameAs Q7525845.
- Sipser–Lautemann_theorem sameAs Théorème_de_Sipser-Gács-Lautemann.
- Sipser–Lautemann_theorem sameAs Teorema_de_Sipser–Lautemann.
- Sipser–Lautemann_theorem sameAs m.08csd9.
- Sipser–Lautemann_theorem sameAs Q7525845.
- Sipser–Lautemann_theorem wasDerivedFrom Sipser–Lautemann_theorem?oldid=684363414.
- Sipser–Lautemann_theorem isPrimaryTopicOf Sipser–Lautemann_theorem.