ECCC-Report TR12-077https://eccc.weizmann.ac.il/report/2012/077Comments and Revisions published for TR12-077en-usMon, 25 Nov 2013 15:14:18 +0200
Comment 2
| Succinct Interactive Proofs for Quantified Boolean Formulas |
Edward Hirsch,
Dieter van Melkebeek,
Alexander Smal
https://eccc.weizmann.ac.il/report/2012/077#comment2In 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.Mon, 25 Nov 2013 15:14:18 +0200https://eccc.weizmann.ac.il/report/2012/077#comment2
Comment 1
| Instance Compression for the Polynomial Hierarchy and Beyond: Erratum |
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2012/077#comment1It 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.Fri, 13 Sep 2013 17:41:46 +0300https://eccc.weizmann.ac.il/report/2012/077#comment1
Paper TR12-077
| Instance Compression for the Polynomial Hierarchy and Beyond |
Chiranjit Chakraborty,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2012/077We 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.Fri, 15 Jun 2012 14:55:12 +0300https://eccc.weizmann.ac.il/report/2012/077