Изменения

Классом сложности <mathtex>PH</mathtex> (англ. polynomial hierarchy) называется объединение классов сложности из [[Полиномиальная иерархия|полиномиальной иерархии]] <mathtex>PH = \cup_{n=0}^{\infty} (\Sigma_n \cup \Pi_n) = \cup_{n=0}^{\infty} \Sigma_n= \cup_{n=0}^{\infty} \Pi_n</tex> Класс <tex>PH</mathtex>в точности совпадает с классом языков, выразимых с помощью логики второго порядка.