The complexity of combinatorial problems with succinct input representation

DOI10.1007/BF00289117zbMATH Open0621.68032MaRDI QIDQ1090455FDOQ1090455

Publication date: 1986

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

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

complexity classes completeness intersection problem initial data membership problem integer expressions Boolean 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)

Cites Work

Cited In (only showing first 100 items - show all)

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

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)