Классы Sigma i и Pi i
Версия от 19:16, 4 сентября 2022; Maintenance script (обсуждение | вклад) (rollbackEdits.php mass rollback)
Пусть имеется предикат
от переменной, вычислимый за полиномиальное время.Классом сложности полиномиальной иерархии
называется класс изКлассом сложности полиномиальной иерархии
называется класс изОбъединением всех классов сложности полиномиальной иерархии является класс PH.
и изАльтернативное определение
Рассмотрим булевы формулы с
предваряющими кванторами. Будем рассматривать каждую формулу как игру двух игроков ( и ) -го порядка. Игра выигрышная для первого игрока ( ), если он начинает игру. В противном случае игра выигрышная для второго игрока ( ).Языком
называется множество игр -го порядка, выигрышных для первого игрока ( ).Языком
называется множество игр -го порядка, выигрышных для второго игрока ( ).Простейшие соотношения
Связь языков из и
Если
, то . Доказательство очевидно из определения и .