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

https://www.youtube.com/watch?v=Ph4hlOzq_pE

by RafelMri • 4 years ago

48 11 4 years ago

youtube.com

throwra620• 4 years ago

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

nomel• 4 years ago

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

paskozdilar• 4 years ago

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.

mcswell• 4 years ago

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

evanb• 4 years ago

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

freemint• 4 years ago

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

waqf• 4 years ago

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

RcouF1uZ4gsC• 4 years ago

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

mbf• 4 years ago

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.

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

Related Stories