文章基本信息

标题：Constructive Separations and Their Consequence
本地全文：下载
作者：Lijie Chen ; Ce Jin ; Rahul Santhanam 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：For a complexity class C and language L, a constructive separation of LC 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 breakthrough separations ranging from EXP=BPP to even P=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=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]. 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 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−P for which there are no constructive separations from any complexity class.
关键词：barriers;circuit complexity;lower bounds;one-tape Turing machine;refuters;streaming