Comment by spooningtamarin | Hacker News Reader

Comment by spooningtamarin | Hacker News Reader

spooningtamarin

There's a common reasoning mistake when it comes to reduction and conclusion of complexity class. You cannot say a problem is NP-complete if you reduced it to an NP-complete problem.

The problem you know is NP-complete has to be reduced to your Santa problem.

What OP described was mapping from Secret Santa to Hamiltonian circuit, not the other way around.

I've had a bunch of problems reduced to be solvable with approximation algorithms of NP-hard problems, that doesn't make them NP-hard, it's equivalent to solving a problem by reducing it to an NP-complete one with an exponential algorithm.

That's why it's not that simple to prove a problem NP-complete.

It might be that the problem is filled with symmetry and by modifying an algorithm for an NP-complete problem you get a polynomial one.

For example, Vehicle Routing Problem with Time Windows (multiple Hamiltonians with time windows) is considered NP-hard but if your locations had a lot of short time windows you can solve any instance in polynomial time (almost O(n)). But you can also solve it with any VRPTW algorithm (DP, PTAS, heuristics etc.).

For the problem to be NP-Complete, it would have to be both in NP (the one thing that can be agreed on) and NP-hard. For it to be NP-hard, every problem in NP would have to be reducible to it. If we already know that the Hamiltonian circuit verification problem is NP-complete, and that the Secret Santa problem is NP, we de-facto know that S.S. is reducible to the Hamiltonian circuit. So the 'Aha' moment in the third to last paragraph is not new information.

It's true that if every NP problem were reducible to S.S., then it would be NP-hard, and as it can be verified in P time with the S.S. list and the list of people plus relations, and is thus in NP, it would also be NP-complete. It would also suffice to reduce an NP-complete problem to the S.S. problem as pictured here to prove NP-completeness.

But this article doesn't give proof of either and generally points in a different direction, like you said, so the title is really misleading and it would have been better to open the article with a question or discussion.

To summarize, this post by Rod Hilton is pretty useful in understanding the relation between P, NP, NP-hard, and NP-complete: http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...

I don't think that's the mistake involved.

Rather, he simply (incorrectly as others have pointed out) asserts a 1-1 map between his problem and the Hamiltonian circuit problem. IE: "A Hamiltonian circuit is a path that traverses an entire graph by visting each node exactly one time. It turns out that this is exactly the problem I was trying to solve. " (exactly his problem equals, has a 1-1 map to Hamiltonian circuits).

Edit: his problem doesn't map either way to the Hamiltonian graph problem - you could have two disjoint graphs that could be solved as Secret Santa problems but not as Hamiltonian graph problems.

Reply on news.ycombinator.com