4 ms·
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
by MichailP 14y ago
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?
- corresation 14y agoIt's is a Clay Mathematics MP problem- http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/
- jtoohill 14y agoIt 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 http://en.wikipedia.org/wiki/Travelling_salesman_problem
- MichailP 14y agoSay 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 :)
- paulgb 14y agoAny NP-Complete problem will have cases that are trivial. The complexity of the problems is how they grow in the worst case.
- rfurmani 14y agoCorrection: 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
- paulgb 14y agoInteresting. 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?
- cpressey 14y agoTo 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.