PH =? PSPACE/решение Сеилов

Материал из DISCOPAL
< PH =? PSPACE
Версия от 16:22, 13 мая 2017; Темирлан (обсуждение | вклад) (Новая страница: «в одной из задач было показано, что PH содержится в PSPACE. покажем, что это если PH = PSPACE, то пол…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

в одной из задач было показано, что PH содержится в PSPACE. покажем, что это если PH = PSPACE, то полиномиальная иерархия схлопывается. от противного. тогда PH = PSPACE. Известно, что в PSPACE есть задача, полная относительно полиномиальной сводимости - это TQBF - полиномиальные предикаты, перед которыми стоят чередующиеся кванторы существования и всеобщности. Если PSPACE = PH, то TQBF будет полным и в PH - но в одной из задач было показано, что Если в PH есть язык, полный относительно полиномиальной сводимости, то полиномиальная иерархия схлопывается, что и требовалось.