The Power of Constructing Bad Inputs

Abstract

A lower bound, showing that a function f cannot be computed by some class C of algorithms, necessarily shows that for every algorithm A in C, there must exist a “bad” input x such that f (x) , A(x). We consider the computational complexity of generating such bad inputs for a given f and class C, and we study how the complexity of this task relates to existing (and major open problems in) lower bounds.