pith. sign in

arxiv: 1012.2394 · v1 · pith:NNLXBFNInew · submitted 2010-12-10 · 💻 cs.CC

NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

classification 💻 cs.CC
keywords subseteqceilingclasslanguagesnonexponentially-dense-classcomplexitycomputationalconstant
0
0 comments X
read the original abstract

A 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_(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)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.