0
$\begingroup$

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}$?

$\endgroup$
9
  • 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, 2015 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$
    – Turbo
    Dec 30, 2015 at 3:47
  • $\begingroup$ That implication is probably true, since its conclusion is probably true. $\endgroup$
    – user12859
    Dec 30, 2015 at 4:33
  • $\begingroup$ @RickyDemer ' probably true' is different from already known. is it not already known? $\endgroup$
    – Turbo
    Dec 30, 2015 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, 2015 at 4:51

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\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$
    – Turbo
    Dec 31, 2015 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$ Dec 31, 2015 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$
    – Turbo
    Dec 31, 2015 at 2:20

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.