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

complexity classescompletenessintersection probleminitial datamembership probleminteger expressionsBoolean expressionsMeyer-Stockmeyer hierarchy\({\mathcal N}{\mathcal P}\)-complete\({\mathcal P}\)-completecardinality problemcounting quantifiergeneral hierarchic input languagesLOGSPACEnonemptiness problem

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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

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)