Teorema de Toda

El teorema de Toda es un resultado de la teoría de la complejidad computacional que fue demostrado por Seinosuke Toda en su artículo "PP es tan difícil como la jerarquía de tiempo polinomial" ^{[ 1 ]} y recibió el Premio Gödel de 1998 .

El teorema afirma que toda la jerarquía polinómica PH está contenida en P ^PP ; esto implica una afirmación estrechamente relacionada, que PH está contenida en P ^#P .

#P es la clase de problemas que consisten en contar exactamente el número de soluciones a una pregunta verificable en tiempo polinomial (es decir, a una pregunta en NP ), mientras que, en términos generales, PP es la clase de problemas para los que existe un algoritmo de tiempo polinomial que proporciona una respuesta correcta más de la mitad de las veces. La clase P ^#P consta de todos los problemas que pueden resolverse en tiempo polinomial si se tiene acceso a respuestas instantáneas a cualquier problema de conteo en #P (tiempo polinomial relativo a un oráculo #P ). Por lo tanto, el teorema de Toda implica que para cualquier problema en la jerarquía polinomial existe una reducción de Turing determinista en tiempo polinomial a un problema de conteo . ^{[ 2 ]}

Un resultado análogo en la teoría de la complejidad sobre los números reales (en el sentido de las máquinas de Turing reales de Blum-Shub-Smale ) fue demostrado por Saugata Basu y Thierry Zell en 2010 ^{[ 3 ]} y un análogo complejo del teorema de Toda fue demostrado por Saugata Basu en 2011. ^{[ 4 ]}

La demostración se divide en dos partes.

• En primer lugar, se establece que

${\displaystyle \Sigma ^{P}\cdot {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$

La demostración utiliza una variación del teorema de Valiant-Vazirani . Porque${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$contiene${\displaystyle {\mathsf {P}}}$y es cerrado bajo complemento, se sigue por inducción que${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$.

• Segundo, se establece que

${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\#P}}$

En conjunto, las dos partes implican

${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\#P}}$

Véase Fortnow 2009 para más detalles. ^{[ 5 ]} Una demostración más pausada se encuentra en el libro de texto Arora & Barak 2009. ^{[ 6 ]}