Title :
The isomorphism conjecture holds and one-way functions exist relative to an oracle
Author_Institution :
Dept. of Comput. Sci., Chicago Univ., IL, USA
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE
Conference_Location :
Minneapolis, MN
Print_ISBN :
0-8186-7052-5
DOI :
10.1109/SCT.1995.514731