TY - GEN
T1 - Separating NE from some nonuniform nondeterministic complexity classes
AU - Fu, Bin
AU - Li, Angsheng
AU - Zhang, Liyu
PY - 2009
Y1 - 2009
N2 - We investigate the question whether NE can be separated from the reduction closures of tally sets, sparse sets and NP. We show that (1)NE ⊈ R no(1) NP-T (TALLY); (2) NE ⊈ Rm SN (SPARSE); and (3) NE ⊈ PnkT /nkNP for all k≥1. Result (3) extends a previous result by Mocas to nonuniform reductions. We also investigate how different an NE-hard set is from an NP-set. We show that for any NP subset A of a many-one-hard set H for NE, there exists another NP subset A′ of H such that A′ ⊇ A and A′-A is not of sub-exponential density.
AB - We investigate the question whether NE can be separated from the reduction closures of tally sets, sparse sets and NP. We show that (1)NE ⊈ R no(1) NP-T (TALLY); (2) NE ⊈ Rm SN (SPARSE); and (3) NE ⊈ PnkT /nkNP for all k≥1. Result (3) extends a previous result by Mocas to nonuniform reductions. We also investigate how different an NE-hard set is from an NP-set. We show that for any NP subset A of a many-one-hard set H for NE, there exists another NP subset A′ of H such that A′ ⊇ A and A′-A is not of sub-exponential density.
UR - https://www.scopus.com/pages/publications/76249103763
U2 - 10.1007/978-3-642-02882-3_48
DO - 10.1007/978-3-642-02882-3_48
M3 - 会议稿件
AN - SCOPUS:76249103763
SN - 3642028810
SN - 9783642028816
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 486
EP - 495
BT - Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings
T2 - 15th Annual International Conference on Computing and Combinatorics, COCOON 2009
Y2 - 13 July 2009 through 15 July 2009
ER -