Institutional Repository
| 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. |
| 内容类型 | 其他 |
| URI标识 | http://ir.iscas.ac.cn/handle/311060/1244 |
| 专题 | 中国科学院软件研究所 |
| 推荐引用方式 GB/T 7714 | Fortune Steven. A Note on the Sparse Complete Sets. 1978-01-01. |
| 条目包含的文件 | ||||||
| 文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
| bj01103435.pdf(295KB) | 开放获取 | 使用许可 | 请求全文 | |||
| 个性服务 |
| 推荐该条目 |
| 保存到收藏夹 |
| 查看访问统计 |
| 导出为Endnote文件 |
| 谷歌学术 |
| 谷歌学术中相似的文章 |
| [Fortune Steven]的文章 |
| 百度学术 |
| 百度学术中相似的文章 |
| [Fortune Steven]的文章 |
| 必应学术 |
| 必应学术中相似的文章 |
| [Fortune Steven]的文章 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论