Mathematical methods in computational complexity.

MaRDI QIDQ4955548zbMATH OpenFDO

Authors A. Bernasconi, Bruno Codenotti, Giovanni Resta

Publication date 28 May 2000

zbMATH Keywords

algebraic compelxityBoolean circuitscomplexity classeslinear transformationsmonotonic circuitsprimality testingprobabilistic algorithms

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Review text

The book presents some classes of mathematical models which can be applied to the evaluation of complexity. It deals with complexity classes, primality testing, probabilistic algorithms, algebraic complexity, linear transformations, Boolean circuits, monotonic circuits and an algebraic characterization of the class \(\text{NC}^{1}\).

Recommendations

• Introduction to circuit complexity. A uniform approach
• Boolean function complexity. Advances and frontiers.
• scientific article; zbMATH DE number 610968

Cited in

(1)

• Matrix methods. An introduction to algebraic complexity

This page was built for publication: Mathematical methods in computational complexity.

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