An exponential lower bound on the size of algebraic decision trees for MAX

DOI10.1007/s000370050010zbMath0918.68032OpenAlexW1524291506MaRDI QIDQ1277095

Marek Karpinski, Andrew Chi-Chih Yao, Dima Yu. Grigoriev

Publication date: 2 February 1999

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050010

zbMATH Keywords

computational complexityhypergraphslower boundsalgebraic decision treesminimal cutsetsMAX problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Randomization and the computational power of analytic and algebraic decision trees ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Complexity lower bounds for approximation algebraic computation trees

This page was built for publication: An exponential lower bound on the size of algebraic decision trees for MAX