Donald Knuth on P=NP at CMU-SV (2014) [video] | Hacker News Reader

Donald Knuth on P=NP at CMU-SV (2014) [video]

youtube.com

48 pointsRafelMri11 comments

If 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

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.

Does someone have a transcript with references to the papers he talks about?

He's talking about the https://en.wikipedia.org/wiki/Robertson–Seymour_theorem.

P = NP only if N is invariant over P and non zero. I don’t get why there’s so much commotion on it

There's $1,000,000 waiting for you [1], if you can prove that.

1. https://en.wikipedia.org/wiki/Millennium_Prize_Problems#P_ve...

I think the original poster was trying to make a more sophisticated version of the classic "P=NP iff P=0 or N=1" joke.

It doesn't sound sophisticated as it doesn't take P=N=0 into account for example. Yours is much better :)

I 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.

My proof is too big for the margins of this window. Guess it's time to get a larger monitor...

True. But also P!=NP if N = (P-1)!

Reply on news.ycombinator.com