Lower Bounds for the Non-Linear Complexity of Algebraic Computation Trees with Integer Inputs.

Michael D. Hirsch

Published in: Comput. Complex. (1991)

Keyphrases

lower bound
worst case
upper bound
decision trees
computational complexity
np hard
branch and bound
linear algebra
vc dimension
complexity measures
tree construction
linear programming relaxation
upper and lower bounds
space complexity
decision problems
tree structure
theoretical analysis