The complexity of combinatorial problems with succinct input representation

DOI10.1007/BF00289117MaRDI QIDQ1090455zbMATHFDO

Authors K. W. Wagner

Publication date 1986

Published in Acta Informatica (Search for Journal in Brave)

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)

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

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)