So I was simply reading up on the P=NP problem and in the article it said that the existence of a one way function would imply that P does not equal to NP.

Of course I read up on it since it was interesting and the definition, at least from my gatherings, is that it is a function that is easily evaluated but not easily inverted roughly speaking.

Well I was mulling it over and I thought about something. Suppose I have a function f that I call a game, that maps natural numbers n to a set A which contains all possible positions the pieces on a chessboard may take.

Define a game to be a function that takes in the number of moves n as an input, and the state the chessboard is in as an output, and that the state of the board evaluated at input n can be legally reached in one move from the state evaluated at input n-1.

Obviously such a function is ‘easy’ to evaluate but given any possible state of a chessboard, there are a multitude of ways to reach it and thus it is definitely much more difficult to evaluate the number of moves required to reach it.

Does such a function count as a one way function?

Btw I don’t know how to tag this so please help if you do thanks.

  • 1
    $\begingroup$ The hard step is making your statement "it is definitely much more difficult" into a rigorous proof. Many have failed at this point. $\endgroup$ – Michal Adamaszek Nov 6 '18 at 11:09
  • $\begingroup$ @Michal Adamaszek well I get that part though I’m not sure how to go about it since I have never studied this subject in depth at all. But at the very least I know it is impossible to figure out how many moves it took to reach a state since you can do things like perpetual checks, giving the same output for many inputs. Though I am sure it is possible to figure out the least number of moves to take to reach it. $\endgroup$ – Horus Nov 6 '18 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.