Valerii Sopin vvs at
Fri Oct 8 01:02:55 EDT 2021

Dear FOM,

Using PSPACE-completeness of quantified boolean logic I have obtained that PH = PSPACE, see

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.

Best Regards,
Valerii Sopin

More information about the FOM mailing list