首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
  • 本地全文:下载
  • 作者:Lijie Chen ; Ron Rothblum ; Roei Tell
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-73
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The Exponential-Time Hypothesis ( ET H ) is a strengthening of the = conjecture, stating that 3 - SA T on n variables cannot be solved in time 2 n , for some 0"> 0 . In recent years, analogous hypotheses that are ``exponentially-strong'' forms of other classical complexity conjectures (such as or co - ) have also been considered. These Exponential-Time Hypotheses have been widely influential across different areas of complexity theory. However, their connections to *derandomization and circuit lower bounds* have yet to be systematically studied. Such study is indeed the focus of the current work, and we prove a sequence of results demonstrating that *the connections between exponential-time hypotheses, derandomization, and circuit lower bounds are remarkably strong*.First, we show that if 3 - SA T (or even TQB F ) cannot be solved by probabilistic algorithms that run in time 2 n polylo g ( n ) , then can be deterministically simulated ``on average case'' in (nearly-)polynomial-time (i.e., in time n polyloglo g ( n ) ). This result addresses a long-standing lacuna in uniform ``hardness-to-randomness'' results, which did not previously extend to such parameter settings. Moreover, we extend this result to support an ``almost-always'' derandomization conclusion from an ``almost-always'' lower bound hypothesis.Secondly, we show that *disproving* certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CircuitSA T for circuits over n bits of size pol y ( n ) can be solved by *probabilistic algorithms* in time 2 n polylo g ( n ) , then does not have circuits of quasilinear size. The main novel feature of this result is that we only assume the existence of a *randomized* circuit-analysis algorithm, whereas previous similar results crucially relied on the hypothesis that the circuit-analysis algorithm does not use randomness.Thirdly, we show that a very weak exponential-time hypothesis is closely-related to the classical question of whether derandomization and circuit lower bounds are *equivalent*. Specifically, we show two-way implications between the hypothesis that the foregoing equivalence holds and the hypothesis that cannot be decided by ``small'' circuits that are *uniformly generated* by relatively-efficient non-deterministic machines. This highlights a sufficient-and-necessary path for progress towards proving that derandomization and circuit lower bounds are indeed equivalent.

  • 关键词:circuit lower bounds ; deradomization ; exponential-time hypothesis
国家哲学社会科学文献中心版权所有