- Teorema de Toda
-
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, PP 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.[1]
Referencias
Categoría:- Teoremas de complejidad computacional
Wikimedia foundation. 2010.