Institutional Repository
| separating ne from some nonuniform nondeterministic complexity classes | |
| Fu Bin; Li Angsheng; Zhang Liyu | |
| 2009 | |
| Conference Name | 15th Annual International Conference on Computing and Combinatorics, COCOON 2009 |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Conference Date | 37450 |
| 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 |
| 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. |
| Sponsorship | State University of New York,; Department of Computer Science and Engineering |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8530 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Fu Bin,Li Angsheng,Zhang Liyu. separating ne from some nonuniform nondeterministic complexity classes[C]. Germany,2009. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment