title: Teorema de Toda
text: # 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.