| Title: | separating ne from some nonuniform nondeterministic complexity classes |
| Author: | Fu Bin
; Li Angsheng
; Zhang Liyu
|
| Source: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| Conference Name: | 15th Annual International Conference on Computing and Combinatorics, COCOON 2009
|
| Conference Date: | 37450
|
| Issued Date: | 2009
|
| Conference Place: | Niagara Falls, NY, United states
|
| Publish Place: | Germany
|
| ISSN: | 3029743
|
| ISBN: | 3642028810
|
| Department: | (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
|
| Sponsorship: | State University of New York,; Department of Computer Science and Engineering
|
| English Abstract: | 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. © 2009 Springer Berlin Heidelberg. |
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/8530
|
| Appears in Collections: | 计算机科学国家重点实验室 _会议论文
|
|
There are no files associated with this item.
|
| Recommended Citation: | |
Fu Bin,Li Angsheng,Zhang Liyu. separating ne from some nonuniform nondeterministic complexity classes[C]. 见:15th Annual International Conference on Computing and Combinatorics, COCOON 2009. Niagara Falls, NY, United states. 37450.
|
|
|
