The complexity of combinatorial problems with succinct input representation

DOI10.1007/BF00289117MaRDI QIDQ1090455zbMATH OpenFDO

Authors K. W. Wagner

Publication date 1986

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00289117

zbMATH Keywords

\({\mathcal N}{\mathcal P}\)-complete\({\mathcal P}\)-completeBoolean expressionscardinality problemcompletenesscomplexity classescounting quantifiergeneral hierarchic input languagesinitial datainteger expressionsintersection problemLOGSPACEmembership problemMeyer-Stockmeyer hierarchynonemptiness problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• scientific article; zbMATH DE number 3874610
• The complexity of some complementation problems
• SOFSEM 2006: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 219271
• The computational complexity of graph problems with succinct multigraph representation
• The complexity of semilinear problems in succinct representation
• A combinatorial approach to complexity
• COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS
• scientific article; zbMATH DE number 3968574
• scientific article; zbMATH DE number 3934404

Cites work

• A decisive characterization of BPP
• BPP and the polynomial hierarchy
• Complete sets and the polynomial-time hierarchy
• Computational Complexity of Probabilistic Turing Machines
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Hierarchical planarity testing algorithms
• scientific article; zbMATH DE number 3883612 (Why is no real title available?)
• scientific article; zbMATH DE number 3874609 (Why is no real title available?)
• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• Log Space Recognition and Translation of Parenthesis Languages
• On counting problems and the polynomial-time hierarchy
• On small generators
• Succinct representations of graphs
• The complexity of computing the permanent
• The complexity of facets (and some facets of complexity)
• The polynomial-time hierarchy

Cited in

(only showing first 100 items - show all)

• Linear connectivity problems in directed hypergraphs
• Some observations on the connection between counting and recursion
• Parallel computation with threshold functions
• More complicated questions about maxima and minima, and some closures of NP
• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• Unambiguous computations and locally definable acceptance types
• On matroids and hierarchical graphs
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Restricted relativizations of probabilistic polynomial time
• Turing machines with few accepting computations and low sets for PP
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Generalizations of Opt P to the polynomial hierarchy
• A note on the permanent value problem
• On the power of enumerative counting
• A uniform approach to define complexity classes
• On the closure of certain function classes under integer division by polynomially-bounded functions
• On sparse hard sets for counting classes
• Graph isomorphism is low for PP
• Succinct representation, leaf languages, and projection reductions
• Succinctness as a source of complexity in logical formalisms
• Gap-definable counting classes
• A note on SpanP functions
• Simple characterizations of \(P(\# P)\) and complete problems
• On closure properties of GapP
• Universally serializable computation
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• The complexity of some complementation problems
• The complexity of Bayesian networks specified by propositional and relational languages
• Competing provers yield improved Karp-Lipton collapse results
• Complexity results for structure-based causality.
• Nonerasing, counting, and majority over the linear time hierarchy
• Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
• The robustness of LWPP and WPP, with an application to graph reconstruction
• On measure quantifiers in first-order arithmetic
• Explainable AI using MAP-independence
• The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
• Handling and measuring inconsistency in non-monotonic logics
• Open-world probabilistic databases: semantics, algorithms, complexity
• The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
• Subroutines in P systems and closure properties of their complexity classes
• Complexity results for probabilistic answer set programming
• On the complexity of inconsistency measurement
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• A complexity theory for feasible closure properties
• Same-decision probability: a confidence measure for threshold-based decisions
• Characterising the complexity of tissue P systems with fission rules
• The effect of combination functions on the complexity of relational Bayesian networks
• The minimum oracle circuit size problem
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• A parametric analysis of the state-explosion problem in model checking
• Most frugal explanations in Bayesian networks
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• Subtractive reductions and complete problems for counting complexity classes
• Relativized counting classes: Relations among thresholds, parity, and mods
• The complexity of searching implicit graphs
• Motivating explanations in Bayesian networks using MAP-independence
• Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
• Solution-Graphs of Boolean Formulas and Isomorphism
• Languages represented by Boolean formulas
• On stopping evidence gathering for diagnostic Bayesian networks
• Permanent does not have succinct polynomial size arithmetic circuits of constant depth
• Dependence logic with a majority quantifier
• scientific article; zbMATH DE number 3883612 (Why is no real title available?)
• Succinct representations of graphs
• scientific article; zbMATH DE number 3874610 (Why is no real title available?)
• scientific article; zbMATH DE number 4213461 (Why is no real title available?)
• scientific article; zbMATH DE number 3968574 (Why is no real title available?)
• SeparatingPH fromPP by relativization
• On the power of deterministic reductions to C=P
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• On the complexity of graph reconstruction
• Most probable explanations in Bayesian networks: complexity and tractability
• Restrictive Acceptance Suffices for Equivalence Problems
• Interpolation in Valiant's theory
• The consequences of eliminating NP solutions
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
• The complexity of searching succinctly represented graphs
• Bounded queries to arbitrary sets
• scientific article; zbMATH DE number 4115979 (Why is no real title available?)
• On the power of generalized Mod-classes
• Lower bounds against weakly-uniform threshold circuits
• Relationships among $PL$, $\#L$, and the determinant
• The robustness of LWPP and WPP, with an application to graph reconstruction
• Solution-Graphs of Boolean Formulas and Isomorphism1
• On matroids and hierarchical graphs
• Graph isomorphism is low for PP
• The complexity of SORE-definability problems
• The operators min and max on the polynomial hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES
• Counting classes: Thresholds, parity, mods, and fewness
• Graph Ramsey theory and the polynomial hierarchy
• Dot operators
• On counting propositional logic and Wagner's hierarchy
• A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
• Structural complexity of rational interactive proofs
• On measuring inconsistency in definite and indefinite databases with denial constraints
• A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
• Extensions of MSO and the monadic counting hierarchy

This page was built for publication: The complexity of combinatorial problems with succinct input representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090455)