La hiérarchie polynômiale est une hiérarchie de classes de complexité de problèmes, qui étend la notion de classes P, NP, co-NP.
On peut définir la hiérarchie à l'aide des quanteurs pour-tout et il-existe. Soit p un polynôme (Un polynôme, en mathématiques, est la combinaison linéaire des produits de...), et L un langage.
c'est-à-dire que quand il existe un mot w relativement petit (polynômialement) qui peut en témoigner. De la même façon on définit
On étend ces définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) aux classes de langages : ainsi
Alors, on peut enfin donner les définitions des classes de la hiérarchie polynômiale par
En particulier, et .
La hiérarchie polynômiale est également définissable à l'aide de machine de Turing (Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques...) avec oracle. AB dénote la classe des machines de complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...) P augmentées d'un oracle de complexité B.
On pose
Puis pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) i≥0 :