Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.

Scott Diehl Dieter van Melkebeek

Published in: SIAM J. Comput. (2006)

Keyphrases

lower bound
randomized algorithm
upper bound
min sum
space time
special case
search space
hierarchical structure
branch and bound algorithm
worst case
objective function
quadratic assignment problem
low dimensional
lower and upper bounds
linear space
vector space
lower level
computational complexity
optimal solution