Title :
On honest polynomial reductions, relativizations, and P=NP
Author :
Downey, Rod ; Homer, Steven ; Gasarch, William I. ; Moses, Michael
Author_Institution :
Dept. of Math., Victoria Univ., Wellington, New Zealand
Abstract :
The authors prove a number of structural theorems about the honest polynomial m-degrees, contingent on the assumption P=NP (or a unary alphabet). The ultimate goal would be to prove a contradiction from P=NP. They show that low sets cannot be minimal with respect. They also show that some theorems about honest polynomial reductions do not relativize; hence, techniques in this area may be able to resolve the P=NP question. They examine an alternative definition of honest m -reduction under which recursive minimal sets can be constructed
Keywords :
computational complexity; polynomials; honest m-reduction; honest polynomial reductions; polynomial m-degrees; recursive minimal sets; structural theorems; unary alphabet; Delay; Educational institutions; Injuries; Polynomials; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41825