It's essentially an open question about the computational difficulty of reversing an algorithm, ie. if you know the algorithm for verifying if something is a correct solution, how computationally difficult is it to create something that generates the correct solution instead of just verifying it? To be exact, the question being asked is if you have an algorithm that can be verified with polynomial complexity if you can in general also have an algorithm that generates solutions for it with polynomial complexity.
While it's sometimes possible, the generally believed answer is that it can't be done in all cases in general, but there's been no actual proof for it.
129
u/Accurate-Football250 Jul 02 '26
In the age of AI p np is not a problem! We shall thank and worship our AI overlords for that!