Lijie Chen ; Ce Jin ; Rahul Santhanam ; Ryan Williams - Constructive Separations and Their Consequences

theoretics:9259 - TheoretiCS, February 15, 2024, Volume 3 -
Constructive Separations and Their ConsequencesArticle

Authors: Lijie Chen ; Ce Jin ; Rahul Santhanam ; Ryan Williams

    For a complexity class $C$ and language $L$, a constructive separation of $L \notin 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 \neq BPP$ to even $P \neq NP$. 2. Our second set of results shows that for most major open problems in lower bounds against $P$, $ZPP$, and $BPP$, including $P \neq NP$, $P \neq PSPACE$, $P \neq PP$, $ZPP \neq EXP$, and $BPP \neq NEXP$, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for $P \neq NP$ [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and $BPP \neq 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.

    Volume: Volume 3
    Published on: February 15, 2024
    Accepted on: January 24, 2024
    Submitted on: March 29, 2022
    Keywords: Computer Science - Computational Complexity
      Source : OpenAIRE Graph
    • AF: Small: Lower Bounds in Complexity Theory Via Algorithms; Funder: National Science Foundation; Code: 2127597
    • AF: Small: Average-Case Fine-Grained Complexity; Funder: National Science Foundation; Code: 1909429

    Consultation statistics

    This page has been seen 142 times.
    This article's PDF has been downloaded 95 times.