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$.



Logical complexity of hard functions conjectures
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](https://mathoverflow.net/questions/57345/examples-of-g-delta-sets/57348#comment144034_57348) 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$.


