NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

Details NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

2010-12-10

arxiv.org/abs/1012.2394v1

Computer Science

Computational Complexity

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105257