## Instance compression of parametric problems and related hierarchies

##### Download

Chakraborty2014.pdf (1.117Mb)

##### Date

2014-06-27##### Author

Chakraborty, Chiranjit

##### Metadata

Show full item record##### Abstract

We define instance compressibility ([13, 17]) for parametric problems in the classes
PH and PSPACE.We observe that the problem ƩiCIRCUITSAT 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 Ʃp/i 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 Ʃ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 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 ([11, 6]) , we show that QBCNFSAT (Quantified Boolean Formula
(in CNF) Satisfiability) is in Succinct IP. On the contrary if QBCNFSAT has Succinct
PCPs ([32]) , Polynomial Hierarchy (PH) collapses.
After extending the notion of instance compression to higher classes, we study the
hierarchical structure of the parametric problems with respect to compressibility. For
that purpose, we extend the existing definition of VC-hierarchy ([13]) to parametric
problems. After that, we have considered a long list of natural NP problems and tried
to classify them into some level of VC-hierarchy. We have shown some of the new w-reductions
in this context and pointed out a few interesting results including the ones
as follows.
1. CLIQUE is VC1-complete (using the results in [14]).
2. SET SPLITTING and NAE-SAT are VC2-complete.
We have also introduced a new complexity class VCE in this context and showed
some hardness and completeness results for this class. We have done a comparison
of VC-hierarchy with other related hierarchies in parameterized complexity domain as
well.
Next, we define the compression of counting problems and the analogous classification
of them with respect to the notion of instance compression. We define #VC-hierarchy
for this purpose and similarly classify a large number of natural counting
problems with respect to this hierarchy, by showing some interesting hardness and
completeness results.
We have considered some of the interesting practical problems as well other than
popular NP problems (e.g., #MULTICOLOURED CLIQUE, #SELECTED DOMINATING
SET etc.) and studied their complexity for both decision and counting version. We have
also considered a large variety of circuit satisfiability problems (e.g., #MONOTONE
WEIGHTED-CNFSAT, #EXACT DNF-SAT etc.) and proved some interesting results
about them with respect to the theory of instance compressibility.