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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.