vvs at myself.com
Fri Oct 8 01:02:55 EDT 2021
Using PSPACE-completeness of quantified boolean logic I have obtained that PH = PSPACE, see https://arxiv.org/abs/1411.0628
The idea is the following:
1) the quantified Boolean formula problem is equivalent to existing of boolean functions for each variable with the quantifier ∃, which make
the formula to be Tautology (Skolem functions).
2) size of boolean functions can be exponential, but it is considered in frames of full DNF. It allows to not construct
precisely the boolean functions. Namely, iterations of ∀x∃y reduces to a suitable “long” conjunction of separated ∀x∃y (XOR is the only issue here and it can be handled).
This way PSPASE-complete problem is solved using alternating Turing machine with only 4 alternations.
More information about the FOM