加载中…
A long standing open problem in the computational complexity theory is to separate NE from BPP, which is a subclass of . In this paper, we show that 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 for every time constructible super-polynomial function g(n) such as , where Pad(NP, g(n)) is class of all languages for . We also show .

生成讲解博客的中文版本

生成AI智能校验的中文版本