ECCC-Report TR18-003https://eccc.weizmann.ac.il/report/2018/003Comments and Revisions published for TR18-003en-usThu, 10 Jan 2019 17:33:27 +0200
Revision 4
| Proving that prBPP = prP is as hard as proving that “almost NP” is not contained in P/poly |
Roei Tell
https://eccc.weizmann.ac.il/report/2018/003#revision4What circuit lower bounds are necessary in order to prove that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$? We show that the recent breakthrough result of Murray and Williams (STOC 2018) can be used to show a dramatic strengthening of the previously-known answer to this question. Specifically, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$, for essentially any $f(n)=\omega(1)$.
We also prove a technical strengthening of this result. Specifically, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any $s:\mathbb{N}\rightarrow\mathbb{N}$ it holds that $NTIME[s^{O(1)}\circ s^{O(1)}]\not\subseteq SIZE[s]$. Moreover, we show that size-$s$ circuits fail to compute the ``hard'' function in any interval of length $\poly(s(\poly(n)))$. The proof of this result uses tools of Murray and Williams, but relies on a different proof strategy. (Their proof strategy yields three compositions of $s$ instead of two, and does not yield the guarantee of failure in any small interval.)
Lastly, we present an alternative proof of the main result, which only relies on a generalization of the well-known lower bound of Santhanam (SICOMP, 2009).Thu, 10 Jan 2019 17:33:27 +0200https://eccc.weizmann.ac.il/report/2018/003#revision4
Revision 3
| Proving that prBPP=prP is as hard as "almost" proving that P \ne NP |
Roei Tell
https://eccc.weizmann.ac.il/report/2018/003#revision3What circuit lower bounds are necessary in order to prove that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$? We show that the recent breakthrough result of Murray and Williams (STOC 2018) can be used to show a dramatic strengthening of the previously-known answer to this question. Specifically, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$, for essentially any $f(n)=\omega(1)$.
We also prove several technical strengthenings of this result, which use different proof strategies than the one employed by Murray and Williams. In particular:
1. We prove that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any $s:\mathbb{N}\rightarrow\mathbb{N}$ it holds that $NTIME[s^{O(1)}\circ s^{O(1)}]\not\subseteq SIZE[s]$. Moreover, we show that the failure of size-$s$ circuits to compute the ``hard'' functions happens in any interval of length $\poly(s(\poly(n)))$. (Directly invoking the Murray-Williams tools yields three compositions of $s$ instead of two, and does not yield the guarantee of failure in any small interval.)
2. We prove that under the weaker hypothesis $\mathcal{BPP}=\mathcal{P}$ (i.e., without the promise), one of the following holds: Either for essentially any $s:\mathbb{N}\rightarrow\mathbb{N}$ it holds that $NTIME[s^{O(1)}\circ s^{O(1)}]\not\subseteq SIZE[s]$, or the permanent of $\{0,1\}$-matrices over $\mathbb{Z}$ does not have polynomial-sized arithmetic circuits. This uses a well-known idea of Kabanets and Impagliazzo (2004).
Lastly, we present an alternative proof of the main result, which only relies on a generalization of the well-known lower bound of Santhanam (SICOMP, 2009).Sat, 05 Jan 2019 11:45:31 +0200https://eccc.weizmann.ac.il/report/2018/003#revision3
Revision 2
| Proving that prBPP=prP is as hard as "almost" proving that P \ne NP |
Roei Tell
https://eccc.weizmann.ac.il/report/2018/003#revision2What circuit lower bounds are necessary in order to prove that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$? The main result in this paper is that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then polynomial-sized circuits cannot simulate non-deterministic machines that run in arbitrarily small super-polynomial time (i.e., $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$, for essentially any $f(n)=\omega(1)$). The super-polynomial time bound in the conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without unconditionally proving that $\mathcal{P}\ne\mathcal{NP}$.
This paper is a direct follow-up to the very recent breakthrough of Murray and Williams (ECCC, 2017), in which they proved a new ``easy witness lemma'' for $NTIME[o(2^n)]$. Our main contribution is in highlighting the strong ``barriers'' for proving $pr\mathcal{BPP}=pr\mathcal{P}$ that can be demonstrated using their results (and, as it turns out, also using previous results). We include three proofs of the main theorem: Two proofs that rely on various results from the work of Murray and Williams, and yield stronger forms of the main theorem (i.e., either use a weaker hypothesis or deduce a stronger conclusion); and a third proof that only relies on a generalization of the well-known lower bound of Santhanam (SICOMP, 2009).Sun, 28 Jan 2018 15:50:23 +0200https://eccc.weizmann.ac.il/report/2018/003#revision2
Revision 1
| Proving that prBPP=prP is as hard as "almost" proving that P \ne NP |
Roei Tell
https://eccc.weizmann.ac.il/report/2018/003#revision1The main result in this paper is that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving that polynomial-sized circuits cannot simulate non-deterministic machines that run in arbitrarily small super-polynomial time (i.e., $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$, for essentially any $f(n)=\omega(1)$). The super-polynomial time bound in the conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without unconditionally proving that $\mathcal{P}\ne\mathcal{NP}$.
This paper is a direct follow-up to the very recent breakthrough of Murray and Williams (ECCC, 2017), in which they proved a new ``easy witness lemma'' for $NTIME[o(2^n)]$. Our main contribution is conceptual, in highlighting the strong ``barriers'' for proving $pr\mathcal{BPP}=pr\mathcal{P}$ (and even for proving much weaker statements) that can be demonstrated using their techniques. Following their approach, we apply the new lemma within the celebrated proof strategy of Williams (SICOMP, 2013), and derive the main result by using a parameter setting that is different than the ones they considered. We also include an alternative proof of the main theorem, which does not rely on the work of Murray and Williams, but rather uses a modification of the well-known lower bound of Santhanam (SICOMP, 2009).Mon, 15 Jan 2018 19:32:47 +0200https://eccc.weizmann.ac.il/report/2018/003#revision1
Paper TR18-003
| Proving that prBPP=prP is as hard as "almost" proving that P \ne NP |
Roei Tell
https://eccc.weizmann.ac.il/report/2018/003We show that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving circuit lower bounds that almost yield that $\mathcal{P}\ne\mathcal{NP}$. More accurately, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without \emph{unconditionally} proving that $\mathcal{P}\ne\mathcal{NP}$.
This paper is a direct follow-up to the very recent breakthrough of Murray and Williams (ECCC, 2017), in which they proved a new ``easy witness lemma'' for $NTIME[o(2^n)]$. Following their approach, we apply the new lemma within the celebrated proof strategy of Williams (SICOMP, 2013), and derive our result by using a parameter setting that is different than the ones they considered.Tue, 02 Jan 2018 18:55:14 +0200https://eccc.weizmann.ac.il/report/2018/003