Definability on finite structures and the existence of one-way functions
Erich Grädel · 1994
Craig's interpolation theorem and Beth's definability theorem are classical results in model theory that fail when only finite structures are considered. Gurevich (Toward Logic Tailored for Computational Complexity, Springer Lecture Notes in Mathematics 1104 (1984) 175--216) has shown that for any logic that captures polynomial time, the analogues of these theorems (on finite structures) are equivalent to certain open statements in complexity theory. By results of Grollmann and Selman (Complexity measures for public-key cryptosystems, SIAM J. Computing 17 (1988), 309--335) these statements are false if and only if there exist certain kinds of one-way functions (for polynomial time). We extend these results and give direct proofs of the correspondance between one-way functions for a complexity class C and the definability and interpolation principles for any logic that captures C. 1 Introduction Intuitively a one-way function is a function which is easy to compute and hard ...