Open AccessA Note on Sparse Complete Sets
Author(s) -
Steven Fortune
Publication year - 1979
Publication title -
siam journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.533
H-Index - 122
eISSN - 1095-7111
pISSN - 0097-5397
DOI - 10.1137/0208034
Subject(s) - combinatorics , complement (music) , mathematics , conjecture , set (abstract data type) , time complexity , reduction (mathematics) , np complete , range (aeronautics) , discrete mathematics , polynomial , computer science , mathematical analysis , biochemistry , chemistry , materials science , geometry , complementation , programming language , composite material , gene , phenotype
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom