teorema de toda

La jerarquía polinómica está contenida en la máquina probabilística de Turing en tiempo polinomial.

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 de tiempo polinomial" ^[1] y que recibió el Premio Gödel en 1998 .

Declaración

El teorema establece que toda la jerarquía polinómica PH está contenida en P ^PP ; esto implica una afirmació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 de las veces. 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 polinómico relativo a un oráculo #P ). Así, el teorema de Toda implica que para cualquier problema en la jerarquía polinómica existe una reducción determinista de Turing en tiempo polinomial a un problema de conteo . ^[2]

Saugata Basu y Thierry Zell demostraron un resultado análogo en la teoría de la complejidad sobre los reales (en el sentido de las máquinas reales de Turing de Blum-Shub-Smale ) en 2009 ^[3] y Saugata Basu demostró un análogo complejo del teorema de Toda en 2011. ^[4]

Prueba

La prueba 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 prueba utiliza una variación del teorema de Valiant-Vazirani . Debido a que contiene y es cerrado bajo complemento, se deduce por inducción que . ${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$ ${\displaystyle {\mathsf {P}}}$ ${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$

• En segundo lugar, se establece que

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

Juntas, las dos partes implican

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

Referencias

1. Toda, Seinosuke (octubre de 1991). "El 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.
2. Premio Gödel 1998. Seinosuke Toda
3. Saugata Basu y Thierry Zell (2009); Jerarquía polinómica, números de Betti y un análogo real del teorema de Toda, en Fundamentos de la matemática computacional
4. Saugata Basu (2011); Un análogo complejo del teorema de Toda, en Fundamentos de la matemática computacional