Ir al contenido

Teorema de Toda

De Wikipedia, la enciclopedia libre

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

[editar]