ECCC-Report TR10-196https://eccc.weizmann.ac.il/report/2010/196Comments and Revisions published for TR10-196en-usMon, 13 Dec 2010 23:34:18 +0200
Paper TR10-196
| NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets |
Bin Fu
https://eccc.weizmann.ac.il/report/2010/196A long standing open problem in the computational complexity theory
is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.
In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),
where Nonexponentially-Dense-Class is the class of languages A without exponential density
(for each constant c>0,$|A^{\le n}|\le 2^{n^c}$ for infinitely many integers n).
Our result implies $NE\not\subseteq NP_T({pad(NP, g(n))})$ for every time
constructible super-polynomial function g(n) such as
$g(n)=n^{\ceiling{\log\ceiling{\log n}}}$, where Pad(NP, g(n))
is class of all languages $L_B=\{s10^{g(|s|)-|s|-1}:s\in B\}$ for
$B\in NP$. We also show $NE\not\subseteq NP_T(P_{tt}(NP)\cap Tally)$.
Mon, 13 Dec 2010 23:34:18 +0200https://eccc.weizmann.ac.il/report/2010/196