Teorema lui Toda este un rezultat în teoria complexității , a demonstrat în 1991 de către Seinosuke Toda în articolul său PP este la fel de greu ca Ierarhia polinomul-Time , și care a câștigat autorul său premiul Gödel în 1998.
Teorema conectează două clase de complexitate , și anume clasele PP și PH . El spune că ierarhia polinomială PH este conținută în P PP care, în plus, este egal cu P #P .
#P este clasa funcțiilor cuvaloare întreagă f pentru care există o mașină de Turing M nedeterministă care funcționează în timp polinomial astfel încât pentru toate x , f ( x ) este numărul de acceptări de execuții pentru M la intrarea x . Prin urmare, clasa de funcții contează numărul de soluții ale unei probleme verificabile în timp polinomial.
PP este clasa problemelor de decizie decise de o mașină Turing nedeterministă în timp polinomial, dintre care majoritatea (mai mult de jumătate) dintre execuții sunt acceptabile.
P #P este clasa problemelor de decizie decise în timp polinomial pe o mașină cu un oracol de clasa #P .
PH este clasa definită ca uniunea claselor ierarhiei polinomiale .
Dovedim că P PP = P #P .
Teorema lui Toda este:
PH ⊆ P #PNu putem compara direct o clasă de probleme de decizie (PH) cu o clasă de funcții (#P). În declarația, #P Oracle este utilizat în clasa P . Aceasta înseamnă că mașina polinomială poate scrie un cuvânt u pe banda sa oracolă și poate obține în timp constant valoarea f ( u ), unde f este o funcție în #P.
Teorema spune, cu alte cuvinte, că pentru orice problemă din ierarhia polinomială, există o reducere polinomială la o problemă de numărare. O demonstrație mai simplă decât demonstrația inițială a fost dată de Fortnow, în 2009.
Un rezultat similar în teoria complexității numerelor reale, semnificația mașinilor Blum-Shub-Smale a fost dovedită de Saugata Basu (în) și Thierry Zell (în) în 2009, și un analog complex al teoremei lui Toda dovedit de Saugata Basu în 2011.