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 P^PP, 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.​

Referencias

• Datos: Q719966