Théorème de Toda
Le théorème de Toda est un résultat en théorie de la complexité, démontré en 1991 par Seinosuke Toda dans son article PP is as Hard as the Polynomial-Time Hierarchy[1], et qui a valu à son auteur le prix Gödel en 1998.
Énoncé informel
Le théorème relie deux classes de complexité, à savoir les classes PP et PH. Il dit que la hiérarchie polynomiale PH est contenue dans PPP qui, par ailleurs, est égale à P#P.
Définitions
#P est la classe des fonctions f à valeurs entières pour lesquelles il existe une machine de Turing non déterministe M fonctionnant en temps polynomial telle que pour tout x, f(x) soit le nombre d'exécutions acceptants pour M sur l'entrée x[2],[3]. C'est donc la classe des fonctions qui compte le nombre de solutions d'un problème vérifiable en temps polynomial.
PP est la classe des problèmes de décision décidés par une machine de Turing non déterministe en temps polynomial, dont la majorité (plus de la moitié) des exécutions sont acceptantes.
P#P est la classe des problèmes de décision décidé en temps polynomial sur une machine disposant d'un oracle de la classe #P.
PH est la classe définie comme l'union des classes de la hiérarchie polynomiale.
On démontre[4] que PPP=P#P.
Énoncé
Le théorème de Toda est :
- PH ⊆ P#P
On ne peut pas comparer directement une classe de problèmes de décision (PH) à une classe de fonctions (#P). Dans l'énoncé, on utilise #P en oracle à la classe P. Cela signifie que la machine polynomiale peut écrire un mot u sur son ruban d'oracle et obtenir en temps constant la valeur f(u), où f est une fonction dans #P[5].
Le théorème dit, en d'autres termes, que pour tout problème dans la hiérarchie polynomiale, il existe une réduction polynomiale à un problème de comptage[6]. Une démonstration plus simple que la démonstration originale a été donnée par Fortnow, en 2009[7].
Extensions
Un résultat analogue dans la théorie de complexité des nombres réels, au sens des machines de Blum-Shub-Smale a été prouvé par Saugata Basu (en) et Thierry Zell (en) en 2009[8], et un analogue complexe du théorème de Toda été prouvé par Saugata Basu en 2011[9].
Références
- Toda 1991.
- Perifel 2014, Section 9.1.1.
- Lane A. Hemaspaandra et Mitsunori Ogihara, « Annexe A10 : #P: Counting functions », dans The complexity theory companion, Springer, , p. 286-287
- Perifel 2014, Exercice 9-N.
- Perifel 2014, Section 9.4.
- Prix Gödel 1998 Laudation Seinosuke Toda
- Fortnow 2009.
- Basu et Zell 2010.
- Basu 2012.
Bibliographie
- Sylvain Perifel, Complexité algorithmique, Paris, Ellipses Marketing, coll. « Références sciences », , 432 p. (ISBN 978-2-7298-8692-9, lire en ligne) — Section 9.4 Théorème de Toda. (La version électronique est datée de .)
- Seinosuke Toda, « PP is as hard as the polynomial-time hierarchy », SIAM Journal on Computing, vol. 20, no 5, , p. 865–877 (DOI 10.1137/0220053, lire en ligne).
- Saugata Basu, « A Complex Analogue of Toda's Theorem », Foundations of Computational Mathematics, vol. 12, no 3, , p. 327-362 (DOI 10.1007/s10208-011-9105-5, lire en ligne)
- Saugata Basu et Thierry Zell, « Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem », Foundations of Computational Mathematics, vol. 10, no 4, , p. 429-454 (DOI 10.1007/s10208-010-9062-4, lire en ligne).
- Lance Fortnow, « A simple proof of Toda's theorem' », Theory of Computing, vol. 5, , p. 135–140 (ISSN 1557-2862, DOI 10.486/toc.2009.v005a007, lire en ligne)
