Hacker News Reader

Comment by ggggtez | Hacker News Reader

That's not NP complete. There are two major differences:

1) it fits exactly.

2) you are told there is an answer

NP complete defines a generalization of a problem. Just because a general problem is hard doesn't mean every set of numbers is the same difficulty.

The problem of course is they are overthinking it using an adult brain. Just think stupid: add toys until you go over, then remove some. Start from largest to smallest. Etc.

View on HN

If we are being technical (and I must assume that we are given that you are making a technical critique), then everything you are claiming is wrong.

1. The phrase “an NP Hard problem” refers to the computational complexity of a problem as the “scale” of the problem goes to infinity. Typically, an author would detail the problem, and what parameters go to infinity, but in this case the general problem “The subset sum problem (SSP)” is well known so explaining details is not necessary.

2. The homework question has two parts. The second part asks “(assume a solution exists) is the solution unique?” Clearly this decision problem reduces to SSP and is NP Hard

By that logic no instance of an NP complete problem is NP complete because you can solve any NP complete problem in finite time, seeing as it's not undecidable.

It just might take longer than the universe will exist for you to get a solution.

The thing is that it being an instance of an NP complete class of problems means that there isn't a guarantee that there is an easy way to find a solution. Meaning, you might have to check every combination - and even if you know there's a valid solution, there's no specific heuristic you can apply in searching the solution space that guarantees that it won't be the very last combination you try.

In particular, notice that the question asks 'is your solution the only one?'

Is there any way, in general, to know you've found all possible valid solutions to this problem without enumerating every single one?

You can prune entire sets of the combination space without needing to enumerate through all of them. One of the simplest such optimizations would be to set that if set S costs more than the target, then no superset of S is a valid solution.

Sure, but that doesn't change the fact that there is no polynomial time algorithm for solving this problem. Your observation makes the problem possible to solve using backtracking (as otherwise there would be an infinity of combinations to check, since we can take multiples of a toy), but does not guarantee it can be solved in a reasonable time.

The problem of finding all the subsets whose value exceeds the limit isn’t necessarily any easier than finding all the subsets whose value equals the limit, is it?

An NP complete problem is not any generalization but a problem where all solutions can be solved using brute force in polynomial time, also representing other problems in the same space. In actuality, an NP complete problem is defined as easy to find a single solution, not that it is difficult to find a solution.

No. If you want an intuitive but also theoretically correct definition of NP, it is the set of problems where it is easy to verify that a given solution is correct. NP - P then is the set of all problems for which it is easy to verify that a solution is correct, but hard to find any solution (this set may be empty, but we haven't proved either way).

Here 'easy' means 'in polynomial time', and the property of all NP problems is that they are solvable in polynomial time given an oracle which generates the solutions, and then verifying that each solution is correct. Equivalently, they are solvable in polynomial time given an infinite number of execution threads that each takes one candidate solution and verifies whether it is correct or not (in polynomial time).

I don't think there is any known class of problems in complexity theory where it is easy to find 1 solution but hard to find all solutions.

Reply on news.ycombinator.com