Constructive Separations and Their Consequences

For a complexity class C and language L, a constructive separation of “L is not in 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. For many separations, making them constructive would imply breakthrough lower bounds. 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 break-through separations ranging from “EXP not equal to BPP” to even “P not equal to NP”. 2. Most conjectured uniform separations can be made constructive. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including “P not equal to NP”, “P not equal to PSPACE”, “P not equal to PP”, “ZPP not equal to EXP”, and “BPP not equal to NEXP”, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for “P not equal to NP” [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and “BPP not equal to NEXP” [Dolev, Fandina and Gutfreund, CIAC 2013]. Thus any proof of these strong lower bounds must also yield a constructive version, compared to many weak lower bounds we currently know. 3. Some separations cannot be made constructive. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions $\mathbf{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. We also show that under plausible conjectures, there are languages in NP - $\mathbf{P}$ for which there are no constructive separations from any complexity class.

Authors

• Lijie Chen 0001
• Ce Jin 0001
• Rahul Santhanam
• R. Ryan Williams

Keywords

• Computer science
• Codes
• Turing machines
• Search problems
• Generators
• Distance measurement
• Complexity theory
• Lower Bound
• Conjecture
• Efficient Algorithm
• Complex Class
• First Set Of Results
• Second Set Of Results
• Time And Space
• Running Time
• Hardness
• Polynomial-time Algorithm
• Complex Circuits
• Proof Of The Existence
• Search Problem
• Non-deterministic Polynomial-time
• Size Formula
• Input Bits
• computational complexity
• lower bounds
• refuters
• circuit complexity
• barriers