A survey of one-way functions in complexity theory

In complexity theory a one-way function is defined to be a one-one, honest, function that is computable in polynomial time whose inverse is not computable in polynomial time. We examine relationships between the complexity of functional computational problems and ordinary set recognition problems. The complexity of inverting one-way functions follows from these relationships. Then we survey various forms of one-way functions that have arisen in relationship to some cryptographic investigations and in relationship to the isomorphism problem.The author acknowledges support by the National Science Foundation under Grant CCR-9002292.