One-way functions and circuit complexity.

A finite function integral is a mapping of {0,1}(n) into {0,1) (m) U{#}, where "#" is a symbol to be thought of a "undefined. " A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial size circuits, but no family of inverses of these functions can be computed with polynonmial size circuits. In this paper we show that (provided functions that are not one-to-one are allowed) one-way functions exist if and only if the satisfiability problem SAT does not have polynomial size circuits.