Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-003 | 28th January 2018 15:50

Proving that prBPP=prP is as hard as "almost" proving that P \ne NP

RSS-Feed




Revision #2
Authors: Roei Tell
Accepted on: 28th January 2018 15:50
Downloads: 157
Keywords: 


Abstract:

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



Changes to previous version:

* Added a third proof of the main theorem, which actually deduces a stronger conclusion.
* The section that discusses the meaning of the new barrier for proving prBPP=prP now appears as Sec 1.3.


Revision #1 to TR18-003 | 15th January 2018 19:32

Proving that prBPP=prP is as hard as "almost" proving that P \ne NP





Revision #1
Authors: Roei Tell
Accepted on: 15th January 2018 19:32
Downloads: 120
Keywords: 


Abstract:

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



Changes to previous version:

* Added Sec 1.1 to discuss the meaning of the new barrier for proving prBPP=prP.
* Added a new and alternative proof of the main theorem (i.e., Thm 1).
* Minor revisions to the high-level exposition.


Paper:

TR18-003 | 2nd January 2018 18:50

Proving that prBPP=prP is as hard as "almost" proving that P \ne NP





TR18-003
Authors: Roei Tell
Publication: 2nd January 2018 18:55
Downloads: 505
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint