Functions definable by arithmetic circuits

DOI10.1007/978-3-642-03073-4_42MaRDI QIDQ3576073zbMATH OpenOpenAlexFDO

Authors Ian Pratt-Hartmann, Ivo Düntsch

Publication date 28 July 2010

Published in Mathematical Theory and Computational Practice (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03073-4_42

zbMATH Keywords

arithmetic circuitcomplex algebraexpressive powerinteger expression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Functions definable by numerical set-expressions
• Complex algebras of arithmetic
• Some results on uniform arithmetic circuit complexity
• On explicit definability in arithmetic
• scientific article; zbMATH DE number 1405642

Cites work

• Classes of Predictably Computable Functions
• Equivalence Problems for Circuits over Sets of Natural Numbers
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1962845 (Why is no real title available?)
• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• On the Computational Completeness of Equations over Sets of Natural Numbers
• On the Recognition of Primes by Automata
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• The bounded arithmetic hierarchy
• The complexity of membership problems for circuits over sets of integers
• The complexity of membership problems for circuits over sets of natural numbers

Cited in

(12)

• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Emptiness problems for integer circuits
• Balance problems for integer circuits
• Functions definable by numerical set-expressions
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• scientific article; zbMATH DE number 1148334 (Why is no real title available?)
• Balance problems for integer circuits
• Emptiness problems for integer circuits
• Complex algebras of arithmetic
• On explicit definability in arithmetic
• A flexible solver for finite arithmetic circuits
• Arithmetic circuits with division

This page was built for publication: Functions definable by arithmetic circuits

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