El teorema de Toda es un resultado de la teoría de la complejidad computacional que fue probado por Seinosuke Toda en su artículo "PP es tan difícil como la jerarquía del tiempo polinomial" [1] y recibió el Premio Gödel 1998 .
Declaración
El teorema establece que toda la jerarquía polinomial PH está contenida en P PP ; esto implica una declaración estrechamente relacionada, que PH está contenido en P #P .
Definiciones
#P es el problema de contar exactamente el número de soluciones a una pregunta polinomialmente verificable (es decir, a una pregunta en NP ), mientras que en términos generales, PP es el problema de dar una respuesta correcta más de la mitad del tiempo. La clase P #P consta de todos los problemas que se pueden resolver 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 ). Así, el teorema de Toda implica que para cualquier problema en la jerarquía polinomial existe una reducción determinista de Turing en tiempo polinomial a un problema de conteo . [2]
Un resultado análogo en la teoría de la complejidad sobre los reales (en el sentido de las máquinas de Turing reales de Blum-Shub-Smale ) fue demostrado por Saugata Basu y Thierry Zell en 2009 [3] y un análogo complejo del teorema de Toda fue probado por Saugata Basu en 2011. [4]
Prueba
La prueba se divide en dos partes.
- Primero, se establece que
- La demostración usa una variación del teorema de Valiant-Vazirani . Porque contiene y está cerrado bajo complemento, se sigue por inducción que .
- En segundo lugar, se establece que
Juntas, las dos partes implican
Referencias
- ^ Toda, Seinosuke (octubre de 1991). "PP es tan difícil como la jerarquía de tiempo polinomial" . Revista SIAM de Computación . 20 (5): 865–877. CiteSeerX 10.1.1.121.1246 . doi : 10.1137 / 0220053 . ISSN 0097-5397 .
- ^ Premio Gödel 1998. Seinosuke Toda
- ^ Saugata Basu y Thierry Zell (2009); Jerarquía polinomial, números Betti y un análogo real del teorema de Toda , en Fundamentos de la matemática computacional
- ^ Saugata Basu (2011); Un análogo complejo del teorema de Toda , en Fundamentos de la matemática computacional