This HTML5 document contains 52 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/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n12https://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/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
dbpedia-zhhttp://zh.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#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Toda's_theorem
rdf:type
yago:Abstraction100002137 yago:WikicatTheoremsInComputationalComplexityTheory yago:Theorem106752293 yago:Communication100033020 yago:Message106598915 yago:Statement106722453 yago:Proposition106750804
rdfs:label
Toda's theorem 戶田定理 Théorème de Toda Teorema de Toda
rdfs:comment
El teorema de Toda es un teorema demostrado por Seinosuke Toda en el artículo de 1991 "PP is as Hard as the Polynomial-Time Hierarchy", que le dio a su autor el Premio Gödel en 1998. El teorema establece que toda la jerarquía polinomial PH está contenida en PPP, lo cual implica que PH está contenido en P#P. Así, el teorema de Toda implica que para cualquier problema en jerarquía polinomial hay una reducción polinomial a un problema de conteo.​ 在理論計算機科學的複雜度理論這一分支中，戶田定理是一個重要的結果，它指出在多項式譜系和之間的內在聯繫： 根據戶田定理，多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：布尔可满足性问题）。戶田定理的証明由在1991年給出，並在1998年為証明者贏得了當年的哥德爾獎。（在1991年的該篇論文中，戶田誠之助實際上證明了（參見：PP），而上述結果是這個結果的一個自然推論。） 戶田定理的証明主要包含以下兩部分： * 一個概率性的証明指出； * 通過去隨機化過程証明上述復雜度類在內。 Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. Le théorème de Toda est un résultat en théorie de la complexité, démontré en 1991 par Seinosuke Toda dans son article PP is as Hard as the Polynomial-Time Hierarchy, et qui a valu à son auteur le prix Gödel en 1998.
dcterms:subject
dbc:Theorems_in_computational_complexity_theory dbc:Structural_complexity_theory
dbo:wikiPageID
18125091
dbo:wikiPageRevisionID
961507308
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem dbr:Sharp-P dbc:Structural_complexity_theory dbr:Blum–Shub–Smale_machine dbr:Polynomial-time_Turing_reduction dbr:Baker-Gill-Solovay_theorem dbr:Computational_complexity_theory dbr:NP_(complexity) dbr:Counting_problem_(complexity) dbr:Seinosuke_Toda dbr:Gödel_Prize dbr:PH_(complexity) dbc:Theorems_in_computational_complexity_theory dbr:Thierry_Zell dbr:PP_(complexity) dbr:Saugata_Basu
owl:sameAs
n12:4toMs yago-res:Toda's_theorem dbpedia-fr:Théorème_de_Toda dbpedia-zh:戶田定理 freebase:m.04cqrx8 wikidata:Q719966 dbpedia-es:Teorema_de_Toda
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Reflist
dbo:abstract
El teorema de Toda es un teorema demostrado por Seinosuke Toda en el artículo de 1991 "PP is as Hard as the Polynomial-Time Hierarchy", que le dio a su autor el Premio Gödel en 1998. El teorema establece que toda la jerarquía polinomial PH está contenida en PPP, lo cual implica que PH está contenido en P#P. #P es el problema de contar el número exacto de soluciones de una pregunta polinomialmente verificable (es decir, de una pregunta en NP), mientras que, a grandes rasgos, es el problema de dar una respuesta que es correcta al menos la mitad de las veces. La clase P#P, finalmente, corresponde a todos los problemas que pueden ser resueltos en tiempo polinomial si se tiene acceso a respuestas instantáneas a cualquier problema de conteo en #P. Así, el teorema de Toda implica que para cualquier problema en jerarquía polinomial hay una reducción polinomial a un problema de conteo.​ Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. 在理論計算機科學的複雜度理論這一分支中，戶田定理是一個重要的結果，它指出在多項式譜系和之間的內在聯繫： 根據戶田定理，多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：布尔可满足性问题）。戶田定理的証明由在1991年給出，並在1998年為証明者贏得了當年的哥德爾獎。（在1991年的該篇論文中，戶田誠之助實際上證明了（參見：PP），而上述結果是這個結果的一個自然推論。） 戶田定理的証明主要包含以下兩部分： * 一個概率性的証明指出； * 通過去隨機化過程証明上述復雜度類在內。 Le théorème de Toda est un résultat en théorie de la complexité, démontré en 1991 par Seinosuke Toda dans son article PP is as Hard as the Polynomial-Time Hierarchy, et qui a valu à son auteur le prix Gödel en 1998.
gold:hypernym
dbr:Result
prov:wasDerivedFrom
wikipedia-en:Toda's_theorem?oldid=961507308&ns=0
dbo:wikiPageLength
3279
foaf:isPrimaryTopicOf
wikipedia-en:Toda's_theorem