Instance Compression for the Polynomial Hierarchy and beyond

We define instance compressibility ([5,7]) for parametric problems in

PH

and

PSPACE

. We observe that the problem Σ

i

CircuitSAT

of deciding satisfiability of a quantified Boolean circuit with

i

 − 1 alternations of quantifiers starting with an existential quantifier is complete for parametric problems in the class

$\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 Σ

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

⊆

NP

/poly and

PH

collapses to the third level.

Next, we define Succinct Interactive Proof (

Succinct IP

) and by adapting the proof of

IP

=

PSPACE

([4,2]), we show that

QBFormulaSAT

(Quantified Boolean Formula Satisfiability) is in

Succinct IP

. On the contrary if

QBFormulaSAT

has

Succinct PCP

s ([11]), Polynomial Hierarchy (

PH

) collapses.