Instance Compression for the Polynomial Hierarchy and Beyond.

Abstract. We define instance compressibility ([1], [7], [5], [6] ) for parametric problems in P H and P SP ACE. We observe that the problem ΣiCircuitSAT of deciding satisfiability of a quantified Boolean circuit with i−1 alternations of quantifiers starting with respect to W-reductions, and that analogously the problem QBCSAT (Quantified Boolean Circuit Satisfiability) is complete for parametric problems in P SP ACE with respect to W-reductions. We show the following results about these problems: 1. CircuitSAT is non-uniformly compressible within NP implies ΣiCircuitSAT 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 P SP ACE ⊆ NP/poly and PH collapses to the third level. Next, we define Succinct IP and show that QBF ormulaSAT (Quantified Boolean Formula Satisfiability) is in Succinct IP. with an existential quantifier is complete for parametric problems in Σ p i 1