Key points are not available for this paper at this time.
Two notions of polynomml time reduclbihty, denoted here by ~ T e and <.~P, were defined by Cook and Karp, respectively The abstract propertms of these two relatmns on the domain of computable sets are investigated. Both relations prove to be dense and to have minimal pairs. Further, there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence. Our method of showing density ymlds the result that if P ~ NP then there are members of NP --P that are not polynomml complete KEY WORDS AND PHRASES polynomial time computation, Turing reduc~billty, many-one reducibility CR CATEGORIES 5 25
Richard E. Ladner (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: