2010/12/10 by Bin Fu, Fu, Bin
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Complexity class #Computational Complexity (cs.CC) #Computer science #Constant (computer programming) #DTIME #Discrete mathematics #FOS: Computer and information sciences #Function (biology) #Mathematics #Time complexity #Turing machine #Universal Turing machine #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1012.2394
arxiv created 2010/12/10 · openalex publication_date 2010/12/10 · arxiv updated 2010/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A long standing open problem in the computational complexity theory is to separate NE from BPP, which is a subclass of NPT(NP∩ P/poly). In this paper, we show that NE\not⊆ NP_(NP ∩ Nonexponentially-Dense-Class), where Nonexponentially-Dense-Class is the class of languages A without exponential density (for each constant c>0,|A≤ n|≤ 2nc for infinitely many integers n). Our result implies NE\not⊆ NPT(pad(NP, g(n))) for every time constructible super-polynomial function g(n) such as g(n)=n^\ceilinglog\ceilinglog n, where Pad(NP, g(n)) is class of all languages LB=\s10g(|s|)-|s|-1:s∈ B\ for B∈ NP. We also show NE\not⊆ NPT(Ptt(NP)∩ Tally).