The Power of Constructing Bad Inputs

Ryan Williams, The Computational Complexity Column by Michal Koucky


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.

Full Text:



  • There are currently no refbacks.