DocumentCode :
2360487
Title :
The isomorphism conjecture holds and one-way functions exist relative to an oracle
Author :
Rogers, John
Author_Institution :
Dept. of Comput. Sci., Chicago Univ., IL, USA
fYear :
1995
fDate :
19-22 Jun 1995
Firstpage :
90
Lastpage :
101
Abstract :
We demonstrate an oracle relative to which there are one-way functions but every paddable 1-li-degree collapses to an isomorphism type, thus yielding a relativized failure of the Joseph-Young (1985) conjecture (JYC). We then use this result to construct an oracle relative to which the isomorphism conjecture (IC) is true but one-way functions exist, which answers an open question of Fenner, Fortnow, and Kurtz (1992). Thus, there are now relativizations realizing every one of the four possible states of affairs between the IC and the existence of one-way functions
Keywords :
computational complexity; computational linguistics; isomorphism conjecture; one-way functions; oracle; paddable 1-li-degree; relativizations; relativized Joseph-Young conjecture failure; Computer science; Polynomials; Terminology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE
Conference_Location :
Minneapolis, MN
ISSN :
1063-6870
Print_ISBN :
0-8186-7052-5
Type :
conf
DOI :
10.1109/SCT.1995.514731
Filename :
514731
Link To Document :
بازگشت