We know $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$ or permanent does not have polynomial sized circuits. However permanent needs superpoly circuits imply $\mathsf{NEXP\not\subseteq P/Poly}$ since $\mathsf{P^{\#P}\subseteq PSPACE\subseteq NEXP}$. So why dont we just say $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$?

  • 1
    $\begingroup$ Where have you seen "... or permanent does not have polynomial sized circuits"? (I've only seen "... or permanent does not have polynomial sized arithmetic circuits".) $\endgroup$ – user12859 Dec 30 '15 at 3:38
  • $\begingroup$ @RickyDemer is it not true if permanent does not have poly size arith ckts then nexp is not in p/poly? $\endgroup$ – 1.. Dec 30 '15 at 3:47
  • $\begingroup$ That implication is probably true, since its conclusion is probably true. $\endgroup$ – user12859 Dec 30 '15 at 4:33
  • $\begingroup$ @RickyDemer ' probably true' is different from already known. is it not already known? $\endgroup$ – 1.. Dec 30 '15 at 4:37
  • $\begingroup$ (Bear in mind that your earlier comment only asked about truth.) Yes, that's not already known. $\endgroup$ – user12859 Dec 30 '15 at 4:51

The conclusion is that the permanent does not have polynomial-size (constant-free) arithmetic circuits or $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$. Permanent not having polynomial-size constant-free arithmetic circuits is not known to imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$.

However, there are a couple more recent similar results whose conclusion is not a disjunction, but simply a lower bound on some polynomial family in $\mathsf{NEXP}$:

  • Jansen and Santhanam showed that if PIT is in $\mathsf{NSUBEXP}$ then there is a family of polynomial whose integer evaluation problem is in $\mathsf{NEXP}$ but which do not have poly-size constant-free arithmetic circuits.

  • Carmosino, Impagliazzo, Kabanets, and Kolokolova show that if PIT over a fixed finite field is in $\mathsf{NSUBEXP}$ then there is a multilinear polynomial whose evaluation problem over that same finite field is in $\mathsf{NE}$ that does not have poly-size arithmetic circuits. (This paper also has many other results of interest, including true hardness-to-randomness equivalences, avoiding many of the usual caveats.)

| cite | improve this answer | |
  • $\begingroup$ @joshuagrchow does $\mathsf{NEXP}$ not having poly-size constant-free arithmetic circuits with some additional condition known to imply $\mathsf{NEXP}\not\subseteq\mathsf{P/poly}$? If so what is that additional condition? $\endgroup$ – 1.. Dec 31 '15 at 1:10
  • 1
    $\begingroup$ @Turbo: Not as far as I know. Most of the big implications show that a Boolean circuit lower bound implies an arithmetic circuit lower bound, not the other way around (which makes sense intuitively, since arithmetic circuits are a restricted model). $\endgroup$ – Joshua Grochow Dec 31 '15 at 2:04
  • $\begingroup$ so moral is the original P=BPP implications is the real deal or else (or anything lower than that) will not have NEXP not in P/Poly as an implication. $\endgroup$ – 1.. Dec 31 '15 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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