文章基本信息

标题：Does Looking Inside a Circuit Help?
本地全文：下载
作者：Russell Impagliazzo ; Valentine Kabanets ; Antonina Kolokolova 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：83
页码：1:1-1:13
DOI：10.4230/LIPIcs.MFCS.2017.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The Black-Box Hypothesisstates 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 neq 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 CSAT. 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 CSAT is solvable by a subexponential-size circuit family. Moreover, if such a counterexample F is symmetric, then CSAT is in Ppoly. These results provide some evidence towards the conjecture (made in this paper) that the Black-Box Hypothesis is false if and only if CSAT is easy.
关键词：Black-Box Hypothesis; Rice's theorem; circuit complexity; SAT; sensitivity of boolean functions; decision tree complexity