Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-077 | 10th June 2012 22:29

Instance Compression for the Polynomial Hierarchy and Beyond



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.


Comment #1 to TR12-077 | 13th September 2013 17:41

Instance Compression for the Polynomial Hierarchy and Beyond: Erratum

Authors: Rahul Santhanam
Accepted on: 13th September 2013 17:41


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.

Comment #2 to TR12-077 | 25th November 2013 15:14

Succinct Interactive Proofs for Quantified Boolean Formulas

Comment #2
Authors: Edward Hirsch, Dieter van Melkebeek, Alexander Smal
Accepted on: 25th November 2013 15:14
Downloads: 5102


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.

ISSN 1433-8092 | Imprint