The complexity of combinatorial problems with succinct input representation
type: Item
instance of: scholarly article
title: The complexity of combinatorial problems with succinct input representation
zbMATH Open document ID: 0621.68032
DOI: 10.1007/BF00289117
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4007726
zbMATH Keywords: counting quantifier
zbMATH Keywords: initial data
zbMATH Keywords: integer expressions
zbMATH Keywords: general hierarchic input languages
zbMATH Keywords: Boolean expressions
zbMATH Keywords: complexity classes
zbMATH Keywords: completeness
zbMATH Keywords: membership problem
zbMATH Keywords: \({\mathcal N}{\mathcal P}\)-complete
zbMATH Keywords: \({\mathcal P}\)-complete
zbMATH Keywords: LOGSPACE
zbMATH Keywords: nonemptiness problem
zbMATH Keywords: intersection problem
zbMATH Keywords: Meyer-Stockmeyer hierarchy
zbMATH Keywords: cardinality problem
author: K. W. Wagner
MaRDI profile type: Publication
cites work: On counting problems and the polynomial-time hierarchy
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q4198056
cites work: Succinct representations of graphs
cites work: BPP and the polynomial hierarchy
cites work: Hierarchical planarity testing algorithms
cites work: Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
cites work: Log Space Recognition and Translation of Parenthesis Languages
cites work: The complexity of facets (and some facets of complexity)
cites work: Q4743737
cites work: On small generators
cites work: Q4131648
cites work: The polynomial-time hierarchy
cites work: The complexity of computing the permanent
cites work: Q3217604
cites work: Q3340148
cites work: Complete sets and the polynomial-time hierarchy
cites work: Q3707407
cites work: A decisive characterization of BPP
Recommended article: Q3340149
Recommended article: The complexity of some complementation problems
Recommended article: SOFSEM 2006: Theory and Practice of Computer Science
Recommended article: Q4694758
Recommended article: The computational complexity of graph problems with succinct multigraph representation
Recommended article: The complexity of semilinear problems in succinct representation
Recommended article: A combinatorial approach to complexity
Recommended article: COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS
Recommended article: Q3735699
Recommended article: Q3706500
description: scientific article; zbMATH DE number 4007726