Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

DOI10.1007/978-3-642-22006-7_59MaRDI QIDQ3012844zbMATH OpenOpenAlexFDO

Authors Stefan Mengel

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• A flexible solver for finite arithmetic circuits
• On the complexity of circuit satisfiability
• Arithmetic circuits: a survey of recent results and open questions
• Mathematical Foundations of Computer Science 2003
• Semidefinite programming and arithmetic circuit evaluation
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Satisfiability of algebraic circuits over sets of natural numbers

Cites work

• A Dichotomy Theorem for Polynomial Evaluation
• Characterizing Valiant's algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Computing Algebraic Formulas Using a Constant Number of Registers
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Fast Parallel Computation of Polynomials Using Few Processors
• On the Desirability of Acyclic Database Schemes
• On the expressive power of CNF formulas of bounded tree- and clique-width
• 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
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Parametrized complexity theory.
• The complexity of acyclic conjunctive queries
• The complexity of satisfiability problems

Cited in

(9)

• A constraint satisfaction approach to a circuit design problem
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Variants of the determinant polynomial and the \textsf{VP}-completeness
• Homomorphism polynomials complete for VP
• Algebraic complexity classes
• The arithmetic complexity of tensor contraction
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• The complexity of weighted counting for acyclic conjunctive queries
• Variants of the determinant polynomial and VP-completeness

This page was built for publication: Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012844)