Bin Fu

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_T (NP \cap$ Nonexponentially-Dense-Class),

where Nonexponentially-Dense-Class is the class of languages A without exponential density

(for ...
more >>>