teorema de Toda - Toda's theorem

Teorema de Toda é um resultado na teoria da complexidade computacional que foi comprovada por Seinosuke Toda em seu artigo "PP é tão duro como o polinômio-Time Hierarquia" (1991) e foi dada a 1998 Prêmio Gödel .

Declaração

O teorema indica que todo o PH hierarquia polinomial está contido em P ^PP ; isto implica uma declaração intimamente relacionados, que PH está contido em P ^#P .

definições

#P é o problema de contar exatamente o número de soluções para uma questão polinomialmente-verificável (isto é, a uma pergunta em NP ), enquanto falando livremente, PP é o problema de dar uma resposta que está correto mais de metade do tempo. A classe P ^#P consiste de todos os problemas que podem ser resolvidos em tempo polinomial, se você tem acesso a respostas instantâneas para qualquer problema de contagem em #P (tempo polinomial em relação a um #P oráculo ). Assim, o teorema de Toda implica que para qualquer problema na hierarquia polinomial há um determinista redução Turing de tempo polinomial para um problema de contagem .

Um resultado semelhante na teoria da complexidade sobre os reais (no sentido de Blum-Shub-Smale máquinas reais de Turing ) foi provado por Saugata Basu e Thierry Zell em 2009 e um análogo complexo do teorema de Toda foi provado por Saugata Basu em 2011.

Prova

A prova é dividida em duas partes.

• Em primeiro lugar, se se provar que

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

A prova usa uma variação do Valiant-Vazirani teorema . Uma vez que contém e é fechado sob complemento, segue-se por indução que .${\ Displaystyle {\ mathsf {BP}} \ cdot \ oplus {\ mathsf {P}}}$${\ Displaystyle {\ mathsf {P}}}$${\ Displaystyle {\ mathsf {PH}} \ subseteq {\ mathsf {BP}} \ cdot \ oplus {\ mathsf {P}}}$

• Em segundo lugar, se se provar que

${\ Displaystyle {\ mathsf {P}} \ cdot \ oplus {\ mathsf {P}} \ subseteq {\ mathsf {P}} ^ {\ afiado P}}$

Juntas, as duas partes implicar

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

Referências