2012/01/20 by Joos Heintz, Heintz, Joos, Bart Kuijpers +4
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #Numerical Methods and Algorithms #Polynomial and algebraic computation #cs.CC
paper · pdf · doi:10.48550/arxiv.1201.4344
37 pages. arXiv admin note: substantial text overlap with arXiv:1110.3030
openalex publication_date 2012/01/20 · arxiv created 2012/04/25 · arxiv updated 2012/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The representation of polynomials by arithmetic circuits evaluating them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.