Arithmetic circuits and polynomial replacement systems

DOI10.1007/3-540-44450-5_13MaRDI QIDQ4472442zbMATH OpenFDO

Authors Pierre McKenzie, Heribert Vollmer, K. W. Wagner

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1974/19740164.htm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Arithmetic Circuits and Polynomial Replacement Systems
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Lower bounds for monotone counting circuits
• Semantical counting circuits

Cited in

(6)

• Characterizing Valiant's algebraic complexity classes
• Arithmetic Circuits and Polynomial Replacement Systems
• Arithmetic and Algebraic Circuits
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Positive and negative proofs for circuits and branching programs
• Integer circuit evaluation is PSPACE-complete

This page was built for publication: Arithmetic circuits and polynomial replacement systems

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