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?

  • $\begingroup$ 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 $\endgroup$
    – Avi Tal
    Commented Sep 15, 2018 at 11:20
  • $\begingroup$ @AviTal See for example this: scholarpedia.org/article/Universal_search $\endgroup$
    – Vanessa
    Commented Sep 16, 2018 at 13:10

1 Answer 1


Yes, such a function was found by Levin himself, published somewhat recently:

The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.

  • $\begingroup$ Thanks! Using Google Scholar, I was able to use this reference to find a reference for a complete public key cryptosystem, by Grigoriev, Hirsch, and Pervyshev, Groups-Complexity-Cryptology 1 (2009), 1-12. $\endgroup$ Commented Sep 15, 2018 at 1:54
  • $\begingroup$ Could you please explain details of this function? As why it aborts after n^2 steps, why to 'preserve a copy of the program prefix and force it, as well as the input length, on the output' and what 'only at places where such possible extension is unique' means exactly. I don't know if this deserves a separate question. $\endgroup$
    – galmeida
    Commented Sep 6, 2019 at 1:46
  • $\begingroup$ @BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/… $\endgroup$
    – galmeida
    Commented Sep 8, 2019 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.