Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
From MaRDI portal
Publication:3012844
DOI10.1007/978-3-642-22006-7_59zbMath1333.68119MaRDI QIDQ3012844
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_59
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
The arithmetic complexity of tensor contraction, The complexity of weighted counting for acyclic conjunctive queries, Some complete and intermediate polynomials in algebraic complexity theory, Unnamed Item, Algebraic Complexity Classes
Cites Work
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Completeness and reduction in algebraic complexity theory
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Characterizing Valiant's algebraic complexity classes
- Parametrized complexity theory.
- On the Desirability of Acyclic Database Schemes
- Fast Parallel Computation of Polynomials Using Few Processors
- A Dichotomy Theorem for Polynomial Evaluation
- The complexity of acyclic conjunctive queries
- Computing Algebraic Formulas Using a Constant Number of Registers
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- The complexity of satisfiability problems
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
