Canada’s top science prize goes to Stephen Cook | Hacker News Reader

Canada’s top science prize goes to Stephen Cook

ottawacitizen.com

58 pointsrpledge11 comments

There are things mentioned in this article that are completely wrong. There are also comments here that show a complete misunderstanding of the P vs. NP question in general, but I won't address these.

The constraint problem here with only pairs of incompatible students is a instance of 2SAT, which is solvable in quadratic time (i.e. in P; note: the complexity here is the possible number of pairs, not just students). To make it reside in NP, it has to be at least 3SAT. Essentially, this is equivalent to also indicating triples of students that are incompatible (while the pairs of any of the students in the triple may or may not be compatible). Since the dean explicitly does not provide this information, we are all good and are in the position of solving this problem efficiently.

Also, Cook did not invent the P vs. NP problem. He is often credited as the person who first formalized it and studied it to a sufficient degree. The first mention of the P vs. NP problem I know of is in a letter from Godel to Von Neumann (http://rjlipton.wordpress.com/about/).

Is example about finding accommodation for 100 from 400 students, given in article, well formulated? Say dean gives you an empty list, then what is so difficult in selecting 100 random students?

It's is a Clay Mathematics MP problem-

http://www.claymath.org/millennium/P_vs_NP/

It is well-formulated. One could come up with instances of other NP-complete problems that have trivial solutions, like "What if there are only two cities and one road between them? Then the Traveling Salesman Problem isn't that hard!" [1]

If the dean gives you a decently sized list, figuring out such an accommodation is very difficult (it grows exponentially with the number of students).

[1] http://en.wikipedia.org/wiki/Travelling_salesman_problem

Say he gives you a list of 300 students who can't go together in rooms. You say, good, I will take the remaining 100 students, and give them rooms. It even has unique solution :)

Any NP-Complete problem will have cases that are trivial. The complexity of the problems is how they grow in the worst case.

Correction: every natural NP-complete problem will have easy cases. You can construct problems for which there is no easy case, which is a shame since I thought at one point you could use this trait to seperate P and NP

Interesting. How do you need to define "easy" for this to work? Can you give an example of a problem without an easy solution? Has this class of problem been studied?

To be precise, the best known solutions to the problem grow exponentially with the number of students. The P ?= NP question is (very roughly speaking) asking if better than exponential solutions exist.

He's a phenomenal lecturer too, I really enjoyed taking both courses I took from him. Well deserved award!

Can't wait for CSC463 !

Reply on news.ycombinator.com