PH =? PSPACE/решение Сеилов — различия между версиями
Материал из DISCOPAL
Темирлан (обсуждение | вклад) (Новая страница: «в одной из задач было показано, что PH содержится в PSPACE. покажем, что это если PH = PSPACE, то пол…») |
(нет различий)
|
Текущая версия на 13:22, 13 мая 2017
в одной из задач было показано, что PH содержится в PSPACE. покажем, что это если PH = PSPACE, то полиномиальная иерархия схлопывается. от противного. тогда PH = PSPACE. Известно, что в PSPACE есть задача, полная относительно полиномиальной сводимости - это TQBF - полиномиальные предикаты, перед которыми стоят чередующиеся кванторы существования и всеобщности. Если PSPACE = PH, то TQBF будет полным и в PH - но в одной из задач было показано, что Если в PH есть язык, полный относительно полиномиальной сводимости, то полиномиальная иерархия схлопывается, что и требовалось.