# Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

• What is the black box hypothesis? I haven't heard of it. Apr 19 '19 at 18:30
• @SashoNikolov, I think they mean Conjecture 5.1 from "On the (Im)possibility of Obfuscating Programs" by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang. See also "Does Looking Inside a Circuit Help?" by Impagliazzo, Kabanets, Kolokolova, McKenzie, and Romani for some connections between versions of BBH and ETH. Apr 20 '19 at 17:47

shows that certain counterexamples to BBH would refute a non-uniform version of ETH (Circuit SAT has $$2^{o(n)}$$ size circuits). They conjecture something like that "non-uniform ETH for Circuit SAT <=> BBH is true".
Note in the other direction, if SETH is false for circuits, this would refute some version of BBH: we cannot possibly solve SAT for black boxes in $$o(2^n)$$ time.