We define instance compressibility for parametric problems in PH and PSPACE. We observe that
the problem \Sigma_{i}CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential uantifier is complete for parametric problems in \Sigma_{i}^{p} with respect to W-reductions, and that analogously the problem QBCSAT (Quantified Boolean Circuit Satisfiability) is complete for parametric problems in PSPACE with respect to W-reductions. We show the following results about these problems:
1) If CircuitSAT is non-uniformly compressible within NP, then \Sigma_{i}CircuitSAT is non-uniformly compressible within NP, for any i >= 1.
2) If QBCSAT is non-uniformly compressible (or even if satisfiability of quantified Boolean CNF formulae is non-uniformly compressible), then PSPACE is contained in NP/poly and PH collapses to the third level.
Next, we define Succinct Interactive Proof (Succinct IP) and scrutinizing the proof of IP = PSPACE, we show that QBFormulaSAT (Quantified Boolean Formula Satisfiability) is in Succinct IP. On the contrary if QBFormulaSAT has Succinct PCPs, Polynomial Hierarchy (PH) collapses.
It was pointed out to us by Alexander Smal and Edward Hirsch (private communication) that the proof of Proposition 6 is incorrect. The proof only gives that validity of quantified Boolean CNF formulas is in succinct IP, not that validity of quantified Boolean formulas is in succinct IP. Hirsch (private communication) has subsequently informed us that Proposition 6 can be re-established using a different arithmetization technique.
In ECCC TR12-077 (Proposition 6), it was claimed that the amount of communication in an interactive protocol for QBFormulaSAT can be bounded by a polynomial in the number of variables in the input formula. However, the proof was flawed. We give two correct proofs of this statement.
