A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
DOI10.1070/SM2012v203n10ABEH004270zbMath1270.68113OpenAlexW2157358149MaRDI QIDQ4907594
Sergey B. Gashkov, Igor S. Sergeev
Publication date: 4 February 2013
Published in: Sbornik: Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1070/sm2012v203n10abeh004270
thin setspermanentcomplexity classesarithmetic circuitsmonotone complexitylower bounds for complexity
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (6)
This page was built for publication: A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials