The complexity of combinatorial problems with succinct input representation (Q1090455)

The following four ways of describing initial data are considered: by integer expressions (IE), general hierarchic input languages (GHIL), Boolean expressions (BE), combinational circuits (CC) versus the usual bitwise way of description and the corresponding complexity classes. Let a description D (in one of the four above ways) give a finite set L(D)\(\subset {\mathbb{N}}\) of natural numbers. For the following problems concerning L(D) and the ways D of description the following completeness results are proved: 1) the membership problem is \({\mathcal N}{\mathcal P}\)- complete for IE and GHIL, is \({\mathcal P}\)-complete for CC, is \({\mathcal L}\)- complete for BE (here \({\mathcal L}\) denotes LOGSPACE); 2) the nonemptiness problem is \({\mathcal L}\)-complete for IE and GHIL, is \({\mathcal N}{\mathcal P}\)- complete for BE and CC; 3) the intersection problem is \({\mathcal N}{\mathcal P}\)-complete for all four ways; 4) the subset and equality problems are \(\Pi_ 2\)-complete for IE and GHIL (here \(\Pi_ 2\) is a member of the Meyer-Stockmeyer hierarchy), are co\({\mathcal N}{\mathcal P}\)-complete for BE and CC. The counting quantifier C is introduced yielding the hierarchy \(C\Sigma_{\kappa}=C\Pi_{\kappa}\subseteq \vee \Sigma S_{\kappa}\bigwedge C\Sigma_{\kappa}\) which generalizes the Meyer- Stockmeyer hierarchy. The following completeness results are proved: 1) the cardinality problem is CV\({\mathcal P}\)-complete for IE and GHIL, is C\({\mathcal P}\)-complete for BE and CC; 2) the multiplicity of an element problem is C\({\mathcal P}\)-complete for IE and GHIL. Some other, similar completeness results, are proved, too.