Knuth 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.
11 comments
[ 4.6 ms ] story [ 28.7 ms ] thread1. https://en.wikipedia.org/wiki/Millennium_Prize_Problems#P_ve...
https://www.scottaaronson.com/papers/pnp.pdf
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.