Re: Question about the P vs NP problem

On Dec 7, 5:58 pm, H <h_boutam...@xxxxxxxxxxx> wrote:
On the official web page of the ClayMath institute, that descrribes
the problemhttp://www.claymath.org/millennium/P_vs_NP/.

We have the problem of "organizing a housing accomodations for a group
of ..." .

My question is how to call this NP problem and is it complete ?

Thanks in advance.

If I understand this correctly, then the problem is as follows:

Given is a number N, and a set of N students (here: N = 400).
Given is a number k (here: k = 100).
Given is a set P of pairs of students.

Find a set S of k students, such that for any two elements x and y of
S, (x, y) is not an element of P.

Now consider the graph G, defined by (x, y) element of G iff (x, y) is
not an element of P.
The problem is now: Find a set S of k students such that for any two
elements x and y of S, (x, y) is an element of G.

This is known as the "maximum clique" problem and known to be NP
complete.
The problem as posed seems to be the "maximum independent set"
problem; obviously also NP complete.

.