separating ne from some nonuniform nondeterministic complexity classes

	separating ne from some nonuniform nondeterministic complexity classes
	Fu Bin; Li Angsheng; Zhang Liyu
	2009
会议名称	15th Annual International Conference on Computing and Combinatorics, COCOON 2009
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
会议日期	37450
会议地点	Niagara Falls, NY, United states
出版地	Germany
ISSN	3029743
ISBN	3642028810
部门归属	(1) Dept. of Computer Science, University of Texas, Pan American, TX 78539, United States; (2) Institute of Software, Chinese Academy of Sciences, Beijing, China; (3) Department of Computer and Information Sciences, University of Texas at Brownsville, Brownsville, TX 78520, United States
摘要	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 /nk^NP 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. © 2009 Springer Berlin Heidelberg.
主办者	State University of New York,; Department of Computer Science and Engineering
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8530
专题	基础软件与系统重点实验室
推荐引用方式 GB/T 7714	Fu Bin,Li Angsheng,Zhang Liyu. separating ne from some nonuniform nondeterministic complexity classes[C]. Germany,2009.