DocumentCode :
2517655
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
fYear :
1989
fDate :
19-22 Jun 1989
Firstpage :
196
Lastpage :
207
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
Type :
conf
DOI :
10.1109/SCT.1989.41825
Filename :
41825
Link To Document :
بازگشت