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 function $f:\{0,1\}^*\to\{0,1\}$ computable in $NE \cap CoNE$ that has $2^{\Omega(n)}$ hardness on average.

Q1. Is there any $\Pi_2$ sentence $\psi$ in the language of arithmetic such that we can prove $\mathbb{N}\models \psi \leftrightarrow \phi_1$?
Q2. Is there any $\Pi_2$ sentence $\psi$ in the language of arithmetic such that such that we can prove $\mathbb{N}\models \psi \leftrightarrow \phi_2$?

Actually, I want to know if these conjectures are $\Pi_2$ expressible like $P\not = NP$.
 A: As given, $\phi_1$ and $\phi_2$ are $\Sigma_2$.
They cannot be shown equivalent to $\Pi_2$ statements by any proof that relativizes. This follows by the same argument as in Examples of $G_\delta$ sets or https://cstheory.stackexchange.com/a/16644. We only need to know that the relativized statements are unaffected by a finite change of the oracle (which is obvious), and that either statement can be made true or false by relativization with suitable oracles:


*

*There are oracles $A$ such that $\mathrm{NEXP}^A=\mathrm{BPP}^A$, whence $\mathrm{NEXP}^A\subseteq \mathrm P^A/\mathrm{poly}$, which implies $\neg\phi_i^A$ for $i=1,2$. See e.g. http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html.

*There are oracles $A$ such that some $\mathrm{NP}^A$-language needs relativized circuit size at least $2^{\alpha n}$, for some constant $\alpha>0$: see http://www.sciencedirect.com/science/article/pii/030439759390256S. This implies $\phi_1^A$ and (using the Impagliazzo–Wigderson argument that worst-case and average-case complexity is equivalent for $\phi_1$) also $\phi_2^A$.
