论文标题
建设性的分离及其后果
Constructive Separations and Their Consequences
论文作者
论文摘要
对于复杂性类别$ c $和语言$ l $，$ l \ notin c $的建设性分离提供了有效的算法（也称为拒绝者），以找到每一个试图决定$ l $的$ c $ -algorithm的反例（不良输入）。我们研究问题：哪些下限可以建设性？建设性分离的后果是什么？我们建立一个案例，即“建设性”是我们知道如何证明的许多弱下限之间的分界线，并且针对$ p $，$ zpp $和$ bpp $的强大下限。换句话说，建设性与复杂性障碍相反：这是我们想要下限的属性。我们的结果分为三个类别。 1。我们的第一组结果表明，对于许多针对流媒体算法，一挡板图灵机和查询复杂性以及最小电路尺寸问题的下限，使这些下限的建设性将意味着从$ exp \ ex \ neq bpp到$ p \ p \ neq np $。 2。我们的第二组结果表明，对于$ p $，$ zpp $和$ bpp $的大多数主要开放问题，包括$ p \ neq np $，$ p \ neq pspace $，$ p \ neq pp $，$ zpp \ zpp \ neq exp $和$ bpp \ bpp \ neq \ neq \ neq neq nexp $，任何构建的构造都可以分开。我们的结果概括了$ p \ neq np $ [Gutfreund，Shaltiel和Ta-Shma，CCC 2005]和$ BPP \ neq nexp $ [Dolev，Fandina和Gutfreund，CIAC 2013]。 3。我们的第三组结果表明，不能使某些复杂性分离成为建设性。我们观察到，对于所有超级多个增长的功能$ t $，都没有建设性的分离来检测高$ t $ t $ - kolmogorov复杂性（已知不在$ p $中的任务），无条件地从任何复杂性类别中。
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.
