Institutional Repository
| A Note on the Sparse Complete Sets | |
| Fortune Steven | |
| 1978 | |
| Keyword | Computer Science Technical Report |
| Language | 英语 |
| English Abstract | 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. |
| Content Type | 其他 |
| URI | http://ir.iscas.ac.cn/handle/311060/1244 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Fortune Steven. A Note on the Sparse Complete Sets. 1978-01-01. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| bj01103435.pdf（295KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment