The PI recently discovered a form of one-way function which, if it exists, confirms the Joseph-Young conjecture that there exists a one- way function f and a standard NP-complete set A such that the NP- complete set f(A) is not polynomial-time isomorphic to A. The PI and two coauthors established that, relative to a random oracle, such functions do exist, and hence, in such a relativized world the Joseph- Young conjecture is correct. This project studies the apparent deep conflict between the Berman-Hartmanis isomorphism conjecture and strong one-way and pseudo-random functions. Included in this project is work to: (a) study interconnections between strong one-way functions and other complexity theory issues; (b) formalize and study notions of polynomial-time computable pseudo-random functions that can be used in place of random sets in complexity theoretic random oracle results; and (c) examine conditions under which the Berman-Hartmanis conjecture is confirmed.
