0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/One-way_function, cstheory.stackexchange.com/q/31566/5038, crypto.stackexchange.com/q/45171/351, crypto.stackexchange.com/q/41439/351. In the future I encourage you to search/research more extensively before posting. $\endgroup$
    – D.W.
    Nov 10 at 9:37
  • $\begingroup$ @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. $\endgroup$
    – Zazaeil
    Nov 10 at 9:40
  • 2
    $\begingroup$ We expect you to do a significant amount of research before asking and to share what you have found. See the help center: "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. [...]" $\endgroup$
    – D.W.
    Nov 10 at 9:42
  • 3
    $\begingroup$ The Wikipedia article answers your question and contains a citation to a primary source that you could read. $\endgroup$
    – D.W.
    Nov 10 at 9:45
  • $\begingroup$ @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! $\endgroup$
    – PsySp
    Nov 10 at 11:11

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.