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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Teorema de Toda (es)
- Théorème de Toda (fr)
- Toda's theorem (en)
- 戶田定理 (zh)
|
| rdfs:comment
| - 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. (fr)
- 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. (en)
- 在理論計算機科學的複雜度理論這一分支中，戶田定理是一個重要的結果，它指出在多項式譜系和之間的內在聯繫： 根據戶田定理，多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：布尔可满足性问题）。戶田定理的証明由在1991年給出，並在1998年為証明者贏得了當年的哥德爾獎。（在1991年的該篇論文中，戶田誠之助實際上證明了（參見：PP），而上述結果是這個結果的一個自然推論。） 戶田定理的証明主要包含以下兩部分：
* 一個概率性的証明指出；
* 通過去隨機化過程証明上述復雜度類在內。 (zh)
- 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. (es)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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. (es)
- 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. (fr)
- 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. (en)
- 在理論計算機科學的複雜度理論這一分支中，戶田定理是一個重要的結果，它指出在多項式譜系和之間的內在聯繫： 根據戶田定理，多項式譜系內的所有問題均可以在多項式時間內歸約為求解多項式個（實際上可以規約為1個）“求令給定布爾表達式為真的可能賦值的數量”（#SAT）問題（參見：布尔可满足性问题）。戶田定理的証明由在1991年給出，並在1998年為証明者贏得了當年的哥德爾獎。（在1991年的該篇論文中，戶田誠之助實際上證明了（參見：PP），而上述結果是這個結果的一個自然推論。） 戶田定理的証明主要包含以下兩部分：
* 一個概率性的証明指出；
* 通過去隨機化過程証明上述復雜度類在內。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
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)