Chiranjit Chakraborty, Rahul Santhanam

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 ... more >>>