2026-07-21T12:35:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8097 2024-03-06T10:40:48Z ddc:004 open_access

Does Looking Inside a Circuit Help? Impagliazzo, Russell Kabanets, Valentine Kolokolova, Antonina McKenzie, Pierre Romani, Shadab Black-Box Hypothesis Rice's theorem circuit complexity SAT sensitivity of boolean functions decision tree complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova and Pierre McKenzie and Shadab Romani 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.1 urn:nbn:de:0030-drops-80975 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.1 eng https://creativecommons.org/licenses/by/3.0/legalcode