5 ms·
Donald Knuth on P=NP at CMU-SV (2014) [video]
- throwra620 5y agoP = NP only if N is invariant over P and non zero. I don’t get why there’s so much commotion on it
- nomel 5y agoThere's $1,000,000 waiting for you [1], if you can prove that. 1. https://en.wikipedia.org/wiki/Millennium_Prize_Problems#P_versus_NP https://en.wikipedia.org/wiki/Millennium_Prize_Problems#P_ve...
- paskozdilar 5y agoI think the original poster was trying to make a more sophisticated version of the classic "P=NP iff P=0 or N=1" joke.
- xiphias2 5y agoIt doesn't sound sophisticated as it doesn't take P=N=0 into account for example. Yours is much better :)
- throwthere 5y agoI think this thread has room for 512 characters of jokes. So far we can fit both of those meeting that constraint so no need to choose favorites.
- mcswell 5y agoMy proof is too big for the margins of this window. Guess it's time to get a larger monitor...
- evanb 5y agoTrue. But also P!=NP if N = (P-1)!
- freemint 5y agoDoes someone have a transcript with references to the papers he talks about?
- waqf 5y agoHe's talking about the https://en.wikipedia.org/wiki/Robertson–Seymour_theorem https://en.wikipedia.org/wiki/Robertson–Seymour_theorem.
- RcouF1uZ4gsC 5y agoIf you want a good overview of the P=NP problem that you can read, I found Scott Aaronson’s article very helpful: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
- mbf 5y agoKnuth is brilliant. Who cares if P = NP if you can't find a P time solution without a huge degree. We know that an exponential time solution exists. Given problems in NP have simplifying heuristics that can significantly reduce the search time space for a good answer on real data. I took an optimizing hard problems class in college, 22 years ago. The professor led with a joke that if a student found a polynomial time solution to any of the problems to come see them for extra credit. The class taught us approaches for finding heuristics to get good performance against sample data sets of practical applications in reasonable time. We were graded by how large a data set of the sample sets we could compute by the time the assignment was due. It was a competition against our peers to see who could solve the largest data set.