A Note on the Sparse Complete Sets

ISCAS OpenIR

	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.