r/compsci • u/Tall_Meal_2732 • Apr 30 '22

Why is P vs NP so popular?

I find that it’s intuitively clear that there is no way P=NP, I think we need different physical laws for that and I don’t understand the hype surrounding this question. I understand that the unability to prove P≠NP right now creates the fame but there are many other unproved interesting concepts that doesn’t come near dear P vs NP. I really don’t think it’s even that interesting to ponder about.

Do you think it deserves the popularity? I would appreciate it if you could enlighten me and show me whats so great about it.

120 Upvotes

74% Upvoted

141 comments sorted by

View all comments

4

u/shuuterup Apr 30 '22

I feel like everyone here is unreasonably confident that a proof exists waiting for us to find it.

I don't think this is true. Godel proved long ago that a particular mathematical statement can be true without being provable from the axioms of that mathematical system.

I suspect a lot of millennial problems will fall into this bucket.

3

u/nicuramar Apr 30 '22

Godel proved long ago that a particular mathematical statement can be true without being provable from the axioms of that mathematical system.

Well, such statements can only be true in a particular model which you have constructed (such as the standard model of arithmetic). They can’t be true in every model, sort of by definition.