6
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ In $\mathbb N$? Of course. One of $\bot$ or $\top$ can be taken as $\phi_i$. $\endgroup$ Aug 24, 2017 at 18:51
  • $\begingroup$ @EmilJeřábek: I edited my question. I need an explicit sentence $\psi$ such that we can prove it is equivalent to $\phi_1$ for example. $\endgroup$ Aug 24, 2017 at 19:34
  • $\begingroup$ @EmilJeřábek Are you sure $\phi_i$ is provable in $\mathbb N$? $\endgroup$
    – Fan Zheng
    Aug 25, 2017 at 7:32
  • 1
    $\begingroup$ @FanZheng $\mathbb N$ is a model, not a theory. $\endgroup$ Aug 25, 2017 at 7:59
  • 1
    $\begingroup$ That statement is not $\Pi_2$, but $\Sigma_2$ (just as the original expression): $$\exists n_0\exists \epsilon>0\,\forall n>n_0\text{$L_n$ requires circuits of size $\ge2^{\epsilon n}$}.$$ The two existential quantifiers are extremely important. $\endgroup$ Aug 25, 2017 at 9:57

1 Answer 1

4
$\begingroup$

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:

$\endgroup$
10
  • $\begingroup$ Why the following isn't equivalent to the $\phi_1$? $$\forall c \forall \epsilon(0<\epsilon<1 \to \exists n\forall C(size(C)\leq 2^{cn^\epsilon}\to \text{$C$ does not compute $L_n$}))$$ for a complete language $L\in E$? $\endgroup$ Aug 25, 2017 at 15:46
  • $\begingroup$ Imagine, for example, that the circuit complexity of $L_n$ is $2^{n/\log n}$. Then $\phi_1$ is false, but your formula is true. $\endgroup$ Aug 25, 2017 at 15:51
  • $\begingroup$ does this mean that assuming $size_L(n)$ dominates all elementary functions that are dominated by every $2^{cn}$ does not imply $\phi_1$? $\endgroup$ Aug 25, 2017 at 15:59
  • $\begingroup$ Also, is $$\forall c \forall \epsilon(0<\epsilon<1 \to \exists n\forall C(size(C)\leq 2^{cn^\epsilon}\to \text{$C$ does not compute $L_n$}))$$ sufficient for derandomizing $BPP$? $\endgroup$ Aug 25, 2017 at 16:01
  • 1
    $\begingroup$ On second thought, what I wrote earlier is not right. “$s_L(n)$ dominates all elementary functions that are dominated by every $2^{cn}$” is weaker than $\phi_1$. The correct equivalent is “$s_L(n)$ dominates all elementary functions that are infinitely often below any $2^{cn}$”. That is, $\forall f((\forall c>0\forall n_0\exists n\ge n_0\,f(n)\le2^{cn})\to\exists n_0\forall n\ge n_0\,s_L(n)\ge f(n))$. Yes, it is also equivalent if the last part is replaced with $\exists n_0\,s_L(n_0)\ge f(n_0)$. Either way, it is $\Pi_3$. $\endgroup$ Aug 25, 2017 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.