Hello dear stackexchangers,

I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-vs-np-problem

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

I understand the problem, but in order for the finder to prove he solve the problem, if we take 100 students from 400, how many "incompatible" pairs and how many combinations of 100 students without these pairs should be proposed and generated in order to make something really "probing"? In a polynomial way of course.

Because the statement is not really clear about it, in my humble opinion.

Sincerely yours


Formally, this is a special case of the "$k$-independent set problem", and can be stated as follows:

Given a graph with 400 vertices, can you pick 100 vertices such that no two of them are adjacent?

(A "graph" is a set of vertices (students) and edges (students who are incompatible). Two vertices are "adjacent" if there is an edge between them (they're incompatible).)

You can find easy solutions for some groups of students: for instance, if there are no incompatibilities at all, any choice of 100 students will work. But the difficult problem is solving this in general, coming up with an algorithm that can solve it for any selection of $k$ students from a group of $n$, with a "polynomial runtime" (which basically means it can be solved reasonably quickly even for large values of $n$).

"Proving" that the problem is solved involves a formal mathematical proof, a way of demonstrating that your algorithm works for any group of students, no matter what the incompatibilities are, no matter how many there are, and takes only polynomial time to run.

Examples won't work as a proof, because no matter how many examples you show, it's always possible that your algorithm would fail on the next one you haven't tried.

If you're actually interested in approaching this problem, the formal problem description explains it more thoroughly. (You will need some mathematical background though.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.