News for hackers. Stuff that matters.
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by RcouF1uZ4gsC on Thursday March 10, 2022 @09:14AM (#30627093)
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

Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by mbf on Thursday March 10, 2022 @09:36AM (#30627354)
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.

Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by freemint on Thursday March 10, 2022 @03:52AM (#30624723)
Does someone have a transcript with references to the papers he talks about?
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by waqf on Thursday March 10, 2022 @08:49AM (#30626830)
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by throwra620 on Wednesday March 09, 2022 @09:44AM (#30614911)
P = NP only if N is invariant over P and non zero. I don’t get why there’s so much commotion on it
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by nomel on Wednesday March 09, 2022 @01:05PM (#30617909)
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...

Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by paskozdilar on Thursday March 10, 2022 @08:42AM (#30626763)
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.
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by xiphias2 on Thursday March 10, 2022 @08:55AM (#30626903)
It doesn't sound sophisticated as it doesn't take P=N=0 into account for example. Yours is much better :)
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by throwthere on Thursday March 10, 2022 @09:34AM (#30627319)
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.
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by mcswell on Thursday March 10, 2022 @07:27PM (#30634567)
My proof is too big for the margins of this window. Guess it's time to get a larger monitor...
Re:Donald Knuth on P=NP at CMU-SV (2014) [video] by evanb on Friday March 11, 2022 @02:15AM (#30637216)
True. But also P!=NP if N = (P-1)!