The complexity of combinatorial problems with succinct input representation

DOI10.1007/BF00289117zbMath0621.68032MaRDI QIDQ1090455

Publication date: 1986

Published in: Acta Informatica (Search for Journal in Brave)

completeness Boolean expressions membership problem intersection problem initial data complexity classes integer expressions Meyer-Stockmeyer hierarchy ${\mathcal N}{\mathcal P}$-complete ${\mathcal P}$-complete cardinality problem counting quantifier general hierarchic input languages LOGSPACE nonemptiness problem

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

A note on SpanP functions ⋮ Simple characterizations of $P(\# P)$ and complete problems ⋮ A complexity theory for feasible closure properties ⋮ On closure properties of GapP ⋮ Languages represented by Boolean formulas ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Dependence logic with a majority quantifier ⋮ Same-decision probability: a confidence measure for threshold-based decisions ⋮ Explainable AI using MAP-independence ⋮ Some observations on the connection between counting and recursion ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Parallel computation with threshold functions ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ The logarithmic alternation hierarchy collapses: $A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}$ ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ On the complexity of graph reconstruction ⋮ Characterising the complexity of tissue P systems with fission rules ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ Unambiguous computations and locally definable acceptance types ⋮ The minimum oracle circuit size problem ⋮ Universally serializable computation ⋮ SeparatingPH fromPP by relativization ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ The complexity of searching implicit graphs ⋮ Motivating explanations in Bayesian networks using MAP-independence ⋮ On the power of deterministic reductions to C=P ⋮ 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 ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Unnamed Item ⋮ On the power of generalized Mod-classes ⋮ Most probable explanations in Bayesian networks: complexity and tractability ⋮ The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Handling and measuring inconsistency in non-monotonic logics ⋮ Interpolation in Valiant's theory ⋮ The consequences of eliminating NP solutions ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES ⋮ On matroids and hierarchical graphs ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ Restricted relativizations of probabilistic polynomial time ⋮ Semidefinite programming and arithmetic circuit evaluation ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ Turing machines with few accepting computations and low sets for PP ⋮ On Stopping Evidence Gathering for Diagnostic Bayesian Networks ⋮ The complexity of searching succinctly represented graphs ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Polynomial-time 1-Turing reductions from $\#$PH to $\#$P ⋮ Generalizations of Opt P to the polynomial hierarchy ⋮ A note on the permanent value problem ⋮ Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy ⋮ Three $\sum^ P_ 2$-complete problems in computational learning theory ⋮ On the power of enumerative counting ⋮ Efficient verification of Tunnell's criterion ⋮ A uniform approach to define complexity classes ⋮ On the closure of certain function classes under integer division by polynomially-bounded functions ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ On sparse hard sets for counting classes ⋮ Graph isomorphism is low for PP ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ On the autoreducibility of functions ⋮ Lower bounds and the hardness of counting properties ⋮ Graph Ramsey theory and the polynomial hierarchy ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ On matroids and hierarchical graphs ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Dot operators ⋮ 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 ⋮ Most frugal explanations in Bayesian networks ⋮ On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant ⋮ Unnamed Item ⋮ Complexity results for probabilistic answer set programming ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Probabilistic polynomial time is closed under parity reductions ⋮ An oracle separating $\oplus P$ from $PP^{PH}$ ⋮ Bounded queries to arbitrary sets ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Graph isomorphism is low for PP ⋮ Linear connectivity problems in directed hypergraphs ⋮ On $\text{TC}^0,\text{AC}^0$, and arithmetic circuits ⋮ On the complexity of inconsistency measurement ⋮ Subtractive reductions and complete problems for counting complexity classes ⋮ THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Complexity results for structure-based causality. ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Gap-definable counting classes ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy ⋮ On measure quantifiers in first-order arithmetic ⋮ On measuring inconsistency in definite and indefinite databases with denial constraints

Cites Work

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