Constructive Separations and Their Consequences
share
For a complexity class C and language L, a constructive separation of L ∉ C gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every C-algorithm attempting to decide L. We study the questions: Which lower bounds can be made constructive? What are the consequences of constructive separations? We build a case that "constructiveness" serves as a dividing line between many weak lower bounds we know how to prove, and strong lower bounds against P, ZPP, and BPP. Put another way, constructiveness is the opposite of a complexity barrier: it is a property we want lower bounds to have. Our results fall into three broad categories. 1. Our first set of results shows that, for many well-known lower bounds against streaming algorithms, one-tape Turing machines, and query complexity, as well as lower bounds for the Minimum Circuit Size Problem, making these lower bounds constructive would imply breakthrough separations ranging from EXP ≠ BPP to even P ≠ NP. 2. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including P ≠ NP, P ≠ PSPACE, P ≠ PP, ZPP ≠ EXP, and BPP ≠ NEXP, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for P ≠ NP [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and BPP ≠ NEXP [Dolev, Fandina and Gutfreund, CIAC 2013]. 3. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions t, there are no constructive separations for detecting high t-time Kolmogorov complexity (a task which is known to be not in P) from any complexity class, unconditionally.
READ FULL TEXT