This HTML5 document contains 49 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Sipser–Lautemann_theorem
rdf:type
yago:Theorem106752293 yago:Statement106722453 yago:Proposition106750804 yago:WikicatTheoremsInComputationalComplexityTheory yago:Message106598915 yago:Communication100033020 yago:Abstraction100002137
rdfs:label
Théorème de Sipser-Gács-Lautemann Teorema de Sipser–Lautemann Sipser–Lautemann theorem
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. 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. 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.
dcterms:subject
dbc:Structural_complexity_theory dbc:Theorems_in_computational_complexity_theory dbc:Randomized_algorithms dbc:Articles_containing_proofs
dbo:wikiPageID
2921620
dbo:wikiPageRevisionID
1077984028
dbo:wikiPageWikiLink
dbc:Articles_containing_proofs dbr:Bounded-error_probabilistic_polynomial dbr:Michael_Sipser dbc:Structural_complexity_theory dbr:Exclusive_disjunction dbr:S2P_(complexity) dbr:Polynomial_hierarchy dbr:Péter_Gács dbr:Computational_complexity_theory dbc:Theorems_in_computational_complexity_theory dbr:Clemens_Lautemann dbc:Randomized_algorithms dbr:MA_(complexity) dbr:P_(complexity) dbr:Complement_(complexity)
owl:sameAs
dbpedia-fr:Théorème_de_Sipser-Gács-Lautemann n15:4ubRc wikidata:Q7525845 freebase:m.08csd9 dbpedia-pt:Teorema_de_Sipser–Lautemann
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Su
dbp:b
2
dbp:p
P
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. 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. 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.
prov:wasDerivedFrom
wikipedia-en:Sipser–Lautemann_theorem?oldid=1077984028&ns=0
dbo:wikiPageLength
6261
foaf:isPrimaryTopicOf
wikipedia-en:Sipser–Lautemann_theorem