首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Does Looking Inside a Circuit Help?
  • 本地全文:下载
  • 作者:Russell Impagliazzo ; Valentine Kabanets ; Antonina Kolokolova
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an upper bound on its circuit size. If this hypothesis is true, then P = NP. We focus on the consequences of the hypothesis being false, showing that (under general conditions on the structure of a counterexample) it implies a non-trivial algorithm for Circuit-SAT. More specifically, we show that if there is a property F of boolean functions such that F has high sensitivity on some input function f of subexponential circuit complexity (which is a sufficient condition for F being a counterexample to the Black-Box Hypothesis), then Circuit-SAT is solvable by a subexponential-size circuit family. Moreover, if such a counterexample F is symmetric, then Circuit-SAT is in P/poly. These results provide some evidence towards the conjecture (made in this paper) that the Black-Box Hypothesis is false if and only if Circuit-SAT is easy.

  • 关键词:black-box complexity ; circuit complexity ; Circuit Satisfiability ; SAT algorithms ; Sensitivity ; white-box complexity
国家哲学社会科学文献中心版权所有