Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame Russell Impagliazzo Jan Krajícek Toniann Pitassi Pavel Pudlák Alan R. Woods

Published in: STOC (1992)

Keyphrases

lower bound
upper bound
average case complexity
branch and bound algorithm

objective function
branch and bound
optimal solution
worst case

lower and upper bounds
np hard
optimal cost
quadratic assignment problem

lower bounding
randomly generated problems
exponential size