Класс PH — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 3 участников)
Строка 1: Строка 1:
Классом сложности <math>PH</math> (англ. polynomial hierarchy) называется объединение классов сложности из [[Полиномиальная иерархия|полиномиальной иерархии]] <math>PH = \cup_{n=0}^{\infty} (\Sigma_n \cup \Pi_n) = \cup_{n=0}^{\infty} \Sigma_n = \cup_{n=0}^{\infty} \Pi_n</math>
+
Классом сложности <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

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

Класс [math]PH[/math] в точности совпадает с классом языков, выразимых с помощью логики второго порядка.