# Function that is guaranteed to be one-way if one-way functions exist?

There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time. Essentially, one lists all polynomial time machines and multi-tasks over them.

Is there an analogous trick for one-way functions (or even one-way trapdoor functions)? That is, can we write down a function that, if one-way functions exist, is necessarily a one-way function?

There seems to be no easy way to mimic the P = NP trick. In that case, we can quickly recognize a solution when we get one. But if I multi-task over all polynomial time functions, there's no obvious way to recognize a one-way function when I arrive at one.

If the answer to the above question is no, is there some kind of argument why we can't do it? Maybe writing down such a function would somehow prove that one-way functions exist?

• Hi Timothy Chow, maybe you can help and point to a link where the trick for writing down an algorithm, that if P = NP, solves SAT in polynomial time, is formalized? Thanks allot Commented Sep 15, 2018 at 11:20
• @AviTal See for example this: scholarpedia.org/article/Universal_search Commented Sep 16, 2018 at 13:10