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.<p>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.<p>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 (<a href="http://rjlipton.wordpress.com/about/" rel="nofollow">http://rjlipton.wordpress.com/about/</a>).
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?