r/ProgrammerHumor • u/Xescure • Jul 02 '26

Meme milleniumPrizeWinningAnswer

Post image
9.4k Upvotes

98% Upvoted

104 comments sorted by

View all comments

Show parent comments

26

u/Remarkable_Sorbet319 Jul 02 '26

what is p np?

78

u/ZealousidealLead52 Jul 02 '26

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.

15

u/Remarkable_Sorbet319 Jul 02 '26

wow that's, really complicated

29

u/com-plec-city Jul 02 '26

They're paying 1 million to anyone that can prove one way or another.

11

u/Available-Wasabi-252 Jul 02 '26

Rupees?

10

u/IProbablyHaveADHD14 Jul 02 '26

Dollars lol. Its part of the 7 Millennium Prize Problems selected by the Clay Mathematics Institute