Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
From MaRDI portal
Publication:3012844
DOI10.1007/978-3-642-22006-7_59zbMath1333.68119OpenAlexW1232310145MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (6)
The arithmetic complexity of tensor contraction ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ Variants of the determinant polynomial and the \textsf{VP}-completeness
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
This page was built for publication: Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
