Класс PH — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
Классом сложности <tex>PH</tex> (англ. polynomial hierarchy) называется объединение классов сложности из [[Полиномиальная иерархия|полиномиальной иерархии]] <tex>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</tex> (англ. polynomial hierarchy) называется объединение классов сложности из [[Полиномиальная иерархия|полиномиальной иерархии]] <tex>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</tex> в точности совпадает с классом языков, выразимых с помощью логики второго порядка. | ||
Текущая версия на 19:25, 4 сентября 2022
Классом сложности (англ. polynomial hierarchy) называется объединение классов сложности из полиномиальной иерархии
Класс в точности совпадает с классом языков, выразимых с помощью логики второго порядка.
