Is solving the PvsNP example question a solution to PvsNP?

520 Views Asked by At

This example question was created by the claymath institute. The PvsNP question states, suppose the dean leaves you with a task to house a group of 400 students inside dorms. But there is only enough room for 100 students. And to make things worse , every student has a list of other students that they are incompatable with. And the number of combinations it would take to sort out a perfect 100 students is more than the number of atoms in our known universe. My question is, if I solve this example problem, and I show my solution could solve any variance of this problem, does that mean I solved PvsNP?

1

There are 1 best solutions below

1
On

I believe that this is an example of an NP-complete problem, meaning that if you found a polynomial time algorithm to solve it, then yes, you would have solved $P = NP$.

However, just finding an algorithm (not in polynomial time) does not say anything about P vs. NP.