4 ms·
It 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 o
by jtoohill 14y ago
It 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.