<p>I define a function <code>f</code> to be <strong>one-way</strong> iff for any sufficiently large <code>x</code> computing <code>f(x)</code> bounded by a polynomial, but reversing it (i.e. finding such <code>y</code> that <code>f(x) = f(y)</code>) has no algorithm in <code>P</code> (except, maybe, a negligible probability of guessing <code>y</code> given <code>x</code> was chosen truly randomly).</p>
<p>Clearly, no one-way function can exist if <code>P = NP</code>. The question I am puzzled with is whether <code>P != NP</code> would imply the existence of such a function.</p>
<p>To the best of my thinking, the answer is negative: even if there are problems in <code>NP</code> that do not belong to <code>P</code> we can't know they &quot;reverse&quot; some other problem in <code>P</code>. Am I right?</p>

CC BY-SA 4.0
2023-11-10T09:37:38.620Z
See https://en.wikipedia.org/wiki/One-way_function, https://cstheory.stackexchange.com/q/31566/5038, https://crypto.stackexchange.com/q/45171/351, https://crypto.stackexchange.com/q/41439/351.  In the future I encourage you to search/research more extensively before posting.
D.W.
CC BY-SA 4.0
2023-11-10T09:40:07.560Z
@D.W. I am not only interested in the answer itself, I am interested in the different views of it by different people and their way of thinking. It is a common practice for the SE - to ask questions of that sort inviting people to enlighten others __in their own way__. Also never considered Wikipedia as a reliable source of information. But thanks for the refs to other questions: I couldn't find them.
Zazaeil
CC BY-SA 4.0
2023-11-10T09:42:31.337Z
We expect you to do a significant amount of research before asking and to share what you have found. See the [help/on-topic]: "Questions should be based on knowledge sharing [...] only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. Search to see if your question is already answered somewhere else (e.g. Wikipedia) before asking a question. Try to make your question interesting for others by providing some background knowledge. [...]"
D.W.
CC BY-SA 4.0
2023-11-10T09:45:29.347Z
The Wikipedia article answers your question and contains a citation to a primary source that you could read.
D.W.
CC BY-SA 4.0
2023-11-10T11:11:03.930Z
@D.W. literarily the 2nd paragraph of the wiki article (the 1st source anyone would look at about everything) answers OP's question with references!
PsySp
CC BY-SA 4.0
2023-11-12T06:38:26.687Z
@PsySp, yes, exactly.
D.W.
<complexity-classes><one-way-function>
Assume `P != NP`, does it imply that one-way functions exist?
Zazaeil
# Assume `P != NP`, does it imply that one-way functions exist?

(Asked by: username_0 on 2023-11-10)

I define a function `f` to be **one-way** iff for any sufficiently large `x` computing `f(x)` bounded by a polynomial, but reversing it (i.e. finding such `y` that `f(x) = f(y)`) has no algorithm in `P` (except, maybe, a negligible probability of guessing `y` given `x` was chosen truly randomly).

Clearly, no one-way function can exist if `P = NP`. The question I am puzzled with is whether `P != NP` would imply the existence of such a function.

To the best of my thinking, the answer is negative: even if there are problems in `NP` that do not belong to `P` we can't know they "reverse" some other problem in `P`. Am I right?

**Tags:** complexity-classes, one-way-function

> **Comments:**
> **username_1**: See https://en.wikipedia.org/wiki/One-way_function, https://cstheory.stackexchange.com/q/31566/5038, https://crypto.stackexchange.com/q/45171/351, https://crypto.stackexchange.com/q/41439/351.  In the future I encourage you to search/research more extensively before posting.  
> **username_0**: @username_1 I am not only interested in the answer itself, I am interested in the different views of it by different people and their way of thinking. It is a common practice for the SE - to ask questions of that sort inviting people to enlighten others __in their own way__. Also never considered Wikipedia as a reliable source of information. But thanks for the refs to other questions: I couldn't find them.  
> **username_1**: We expect you to do a significant amount of research before asking and to share what you have found. See the [help/on-topic]: "Questions should be based on knowledge sharing [...] only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. Search to see if your question is already answered somewhere else (e.g. Wikipedia) before asking a question. Try to make your question interesting for others by providing some background knowledge. [...]"  
> **username_1**: The Wikipedia article answers your question and contains a citation to a primary source that you could read.  
> **username_2**: @username_1 literarily the 2nd paragraph of the wiki article (the 1st source anyone would look at about everything) answers OP's question with references!  
> **username_1**: @username_2, yes, exactly.  

---

## 0 answers

