Hacker News Reader

Comment by MichailP | Hacker News Reader

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?

View on HN

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

Say 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 :)

Any NP-Complete problem will have cases that are trivial. The complexity of the problems is how they grow in the worst case.

Correction: 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

Interesting. 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?

To 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.

It's is a Clay Mathematics MP problem-

http://www.claymath.org/millennium/P_vs_NP/

Reply on news.ycombinator.com