<p>Following some direction provided by Yonatan's comment it seems this is exactly the problem of the existence of a <em>worst-case</em> one-way function, which is equivalent to <span class="math-container">$P\ne NP$</span></p>
<p>Ref: <em>A survey of one-way functions in complexity theory</em> Alan L. Selman 1992</p>
<p>Edit: It seems this terminology may not be entirely unambiguous. As far as I can tell, there is the notion of a one-way (deterministic) function in computational complexity theory, which is the notion mentioned by Selman and the one closest to what I am looking for, and the much more common cryptographic notion of a one-way (probabilistic) function.</p>

CC BY-SA 4.0
2021-10-27T11:47:53.897Z
$P \neq NP$ is not known to imply  the existence of one-way functions. This is a long-standing open problem in computational complexity.
Martin Berger
CC BY-SA 4.0
2021-10-28T01:46:10.567Z
@MartinBerger I know $P\ne NP$ does not imply the existence of the much more common average-case one-way functions, but sources I have found state that it does imply the existence of worst-case one-way functions (see the reference given). Is this wrong?
Alexander Tenenbaum
CC BY-SA 4.0
2021-10-28T11:33:21.007Z
Fair enough. I overlooked the "worst case" qualifier. I've taken the liberty to highlight it in your answer. A definition of can be found in [these lecture notes](https://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture3.pdf#page=5), is this the definition you had in mind?
Martin Berger
CC BY-SA 4.0
2021-10-28T17:27:50.127Z
Interesting, that still seems like the wrong notion. [This](https://cstheory.stackexchange.com/a/31579/64854) answer lead me to believe that worst-case OWFs were the deterministic equivalent of average-case ones, and the paper by Selman was linked elsewhere and seems to use the definition I was looking for. I'm asking about a deterministic polytime function with no deterministic polytime inverse (up to trivialities involving large inputs with small outputs), which seems to be what Selman discusses and claims exist iff $P\ne NP$, though it seems these may not be called worst case OWFs.
Alexander Tenenbaum
CC BY-SA 4.0
2021-10-28T21:35:06.117Z
@JoshuaGrochow makes a slightly different claim:  worst-case one-way functions exist if and only if $ \neq $ with the relationship between $NP $ and $UP$ being open.
Martin Berger
CC BY-SA 4.0
2021-10-26T23:22:26.543Z
2021-10-28T19:50:06.347Z
2021-10-28T19:50:06.347Z
Alexander Tenenbaum
<p>I was reading Charles Bennett's Thermodynamics of Computer Science and a passage (p. 926) caught my eye</p>
<blockquote>
<p>The construction of a reversible machine from an irreversible machine implies that the open question, of whether there exists a 1:1 function much easier to compute by an irreversible machine than by any reversible machine, is equivalent to the question of whether there is an easy 1:1 function with a hard inverse.</p>
</blockquote>
<p>I was quite surprised the existence of an easy 1:1 function with a hard inverse was open, and even more surprised at how hard it seemed to find sources on this (though I'm very unfamiliar with this area, so it's wholly possible I was just searching the wrong things). Seeing as this paper is almost 40 years old, I was wondering if this question was still open, and whether any sources discuss it in more depth.</p>

CC BY-SA 4.0
2021-10-26T23:08:34.290Z
Is this different from the question of whether or not [one-way permutations](https://en.wikipedia.org/wiki/One-way_function#Related_concepts) exist?
Yonatan N
CC BY-SA 4.0
2021-10-26T23:14:28.110Z
@YonatanN This seems to be a weaker definition, as one-way functions allow for negligible error. So I suppose there's no way the problem has been answered positively, but it doesn't seem impossible that it's been answered negatively. Thank you for the reference though, it's much closer to anything I found, surprised I missed it!
Alexander Tenenbaum
CC BY-SA 4.0
2021-10-26T23:20:06.950Z
Oh, it seems this is exactly the definition of worst-case one-way function, rather than the more usual average-case one-way function, the existence of which is known to be equivalent to P=NP, so I suppose it is open :)
Alexander Tenenbaum
<cc.complexity-theory><reversible-computing>
An easy computable injection with a hard inverse
Alexander Tenenbaum
# An easy computable injection with a hard inverse

(Asked by: username_0 on 2021-10-26)

I was reading Charles Bennett's Thermodynamics of Computer Science and a passage (p. 926) caught my eye

> The construction of a reversible machine from an irreversible machine implies that the open question, of whether there exists a 1:1 function much easier to compute by an irreversible machine than by any reversible machine, is equivalent to the question of whether there is an easy 1:1 function with a hard inverse.

I was quite surprised the existence of an easy 1:1 function with a hard inverse was open, and even more surprised at how hard it seemed to find sources on this (though I'm very unfamiliar with this area, so it's wholly possible I was just searching the wrong things). Seeing as this paper is almost 40 years old, I was wondering if this question was still open, and whether any sources discuss it in more depth.

**Tags:** cc.complexity-theory, reversible-computing
> **Comments:**
> **username_1**: Is this different from the question of whether or not [one-way permutations](https://en.wikipedia.org/wiki/One-way_function#Related_concepts) exist?  
> **username_0**: @YonatanN This seems to be a weaker definition, as one-way functions allow for negligible error. So I suppose there's no way the problem has been answered positively, but it doesn't seem impossible that it's been answered negatively. Thank you for the reference though, it's much closer to anything I found, surprised I missed it!  
> **username_0**: Oh, it seems this is exactly the definition of worst-case one-way function, rather than the more usual average-case one-way function, the existence of which is known to be equivalent to P=NP, so I suppose it is open :)  

---

## 1 answers

### Answer by username_0 on 2021-10-26. Score: 4

Following some direction provided by Yonatan's comment it seems this is exactly the problem of the existence of a *worst-case* one-way function, which is equivalent to $P\ne NP$

Ref: *A survey of one-way functions in complexity theory* Alan L. Selman 1992

Edit: It seems this terminology may not be entirely unambiguous. As far as I can tell, there is the notion of a one-way (deterministic) function in computational complexity theory, which is the notion mentioned by Selman and the one closest to what I am looking for, and the much more common cryptographic notion of a one-way (probabilistic) function.

> **Comments:**
> **username_2**: $P \neq NP$ is not known to imply  the existence of one-way functions. This is a long-standing open problem in computational complexity.  
> **username_0**: @MartinBerger I know $P\ne NP$ does not imply the existence of the much more common average-case one-way functions, but sources I have found state that it does imply the existence of worst-case one-way functions (see the reference given). Is this wrong?  
> **username_2**: Fair enough. I overlooked the "worst case" qualifier. I've taken the liberty to highlight it in your answer. A definition of can be found in [these lecture notes](https://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture3.pdf#page=5), is this the definition you had in mind?  
> **username_0**: Interesting, that still seems like the wrong notion. [This](https://cstheory.stackexchange.com/a/31579/64854) answer lead me to believe that worst-case OWFs were the deterministic equivalent of average-case ones, and the paper by Selman was linked elsewhere and seems to use the definition I was looking for. I'm asking about a deterministic polytime function with no deterministic polytime inverse (up to trivialities involving large inputs with small outputs), which seems to be what Selman discusses and claims exist iff $P\ne NP$, though it seems these may not be called worst case OWFs.  
> **username_2**: @JoshuaGrochow makes a slightly different claim:  worst-case one-way functions exist if and only if $ \neq $ with the relationship between $NP $ and $UP$ being open.  

---

