A Note on the Sparse Complete Sets
文献类型：其他
| 作者 | Fortune Steven |
| 发布日期 | 1978 |
| 关键词 | computer science technical report |
| 英文摘要 | Hartmanis and Berman have conjectured that all NP-complete sets are polynomial time isomorphic. A consequence of the conjecture is that there are no sparse NP-complete sets. We show that the existence of an NP-complete set whose complement is sparse implies P = NP. We also show that if there is a polynomial time reduction with sparse range to a PTAPE-complete set, then P=PTAPE. Keywords: reduction, polynomial time, nondeterministic polynomial time, complete sets, sparsity. |
| 语种 | 英语 |
| 源URL | [http://124.16.136.157/handle/311060/1244]  |
| 专题 | 软件研究所_软件所图书馆_其他 |
| 推荐引用方式 GB/T 7714 | Fortune Steven. A Note on the Sparse Complete Sets. 1978-01-01. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。