Skip to main content
One more try. The fucking thing works in the preview, but not live.
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon and Lupanov) in $E^{\Sigma^p_2}$: find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$”. (This argument is essentially due to [Kannan](http://dx.doi.org/10.1016/S0019-9958(82\)90382-5)Kannan who states it with $NE^{\Sigma^p_2}\cap coNE^{\Sigma^p_2}$. The strengthening with $E^{\Sigma^p_2}$ is basically folklore, an explicit proof is given in Lemma 2 of Miltersen, Vinodchadran & Watanabe.)

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon and Lupanov) in $E^{\Sigma^p_2}$: find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$”. (This argument is essentially due to [Kannan](http://dx.doi.org/10.1016/S0019-9958(82\)90382-5) who states it with $NE^{\Sigma^p_2}\cap coNE^{\Sigma^p_2}$. The strengthening with $E^{\Sigma^p_2}$ is basically folklore, an explicit proof is given in Lemma 2 of Miltersen, Vinodchadran & Watanabe.)

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon and Lupanov) in $E^{\Sigma^p_2}$: find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$”. (This argument is essentially due to Kannan who states it with $NE^{\Sigma^p_2}\cap coNE^{\Sigma^p_2}$. The strengthening with $E^{\Sigma^p_2}$ is basically folklore, an explicit proof is given in Lemma 2 of Miltersen, Vinodchadran & Watanabe.)

some references
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon and Lupanov) in $E^{\Sigma^p_2}$ (find: find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$. (This argument is essentially due to [Kannan](http://dx.doi.org/10.1016/S0019-9958(82\)90382-5) who states it with $NE^{\Sigma^p_2}\cap coNE^{\Sigma^p_2}$. The strengthening with $E^{\Sigma^p_2}$ is basically folklore, an explicit proof is given in Lemma 2 of Miltersen, Vinodchadran & Watanabe.)

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon) in $E^{\Sigma^p_2}$ (find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$”).

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon and Lupanov) in $E^{\Sigma^p_2}$: find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$. (This argument is essentially due to [Kannan](http://dx.doi.org/10.1016/S0019-9958(82\)90382-5) who states it with $NE^{\Sigma^p_2}\cap coNE^{\Sigma^p_2}$. The strengthening with $E^{\Sigma^p_2}$ is basically folklore, an explicit proof is given in Lemma 2 of Miltersen, Vinodchadran & Watanabe.)

Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon) in $E^{\Sigma^p_2}$ (find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$”).