All Questions
1 question
6
votes
1
answer
172
views
Logical complexity of hard functions conjectures
Let $\phi_1$ and $\phi_2$ be the following statements:
$\phi_1:$ There is a function $f:\{0,1\}^*\to\{0,1\}$ computable in $E$ that has circuit complexity $2^{\Omega(n)}$.
$\phi_2:$ There is a ...
- 1,689