Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes

Philippe Chapdelaine Etienne Grandjean

Published in: CoRR (2006)

Keyphrases

space complexity
lower bound
worst case
upper bound
arc consistency
randomly generated problems
optimization problems
branch and bound
multi class problems