<p>Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you're given a circuit for the function.</p>

<p>The paper:</p>

<p><a href="https://eccc.weizmann.ac.il/report/2017/109/" rel="noreferrer">https://eccc.weizmann.ac.il/report/2017/109/</a></p>

<p>shows that certain counterexamples to BBH would refute a non-uniform version of ETH (Circuit SAT has <span class="math-container">$2^{o(n)}$</span> size circuits). They conjecture something like that "non-uniform ETH for Circuit SAT &lt;=> BBH is true".</p>

<p>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 <span class="math-container">$o(2^n)$</span> time. </p>

CC BY-SA 4.0
2019-04-20T20:35:40.143Z
2019-04-20T20:35:40.143Z
Ryan Williams
<p>Is there a relation between  BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?</p>

CC BY-SA 4.0
2019-04-19T18:30:01.337Z
What is the black box hypothesis? I haven't heard of it.
Sasho Nikolov
CC BY-SA 4.0
2019-04-20T17:47:22.970Z
@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.
Alex Golovnev
<complexity-classes><time-complexity><p-vs-np>
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
user52643
# Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

(Asked by: username_0 on 2019-04-19)

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

**Tags:** complexity-classes, time-complexity, p-vs-np

> **Comments:**
> **username_1**: What is the black box hypothesis? I haven't heard of it.  
> **username_2**: @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.  

---

## 1 answers

### Answer by username_3 on 2019-04-20. Score: 9 | Accepted answer

Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you're given a circuit for the function.

The paper:

<https://eccc.weizmann.ac.il/report/2017/109/>

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.


---

