PH =? PSPACE/решение Сеилов — различия между версиями

Текущая версия на 13:22, 13 мая 2017

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