Sign in to follow this  
EmrldDrgn

NP-complete problems (specifically Subset-sum)

Recommended Posts

First off, let me go on record as saying no, this is NOT homework. I'm interested in NP-complete problems, specifically (at this point) the subset-sum problem. The things I'm specifically interested in right now are: Are simpler cases of NP-complete problems still NP-complete? For instance, if you restrict the subset-sum problem to the case of a set of positive integers summing to a positive integer, is it still NP-complete? Some web resources I've found (like this one) actually define the problem this way, but it seems to me to be not-the-same. Is there some kind of mathematical or computer-science formalism that would need to be used to prove that a proposed polynomial-time solution to an NP-complete problem was a) polynomial-time and b) actually solved the problem in all cases? It seems like there would need to be, but I don't know what it would be, especially since (if I remember correctly) someone (Turing?) proved that not all algorithms can be mathematically proven correct in all cases. (The previous statement could be completely wrong. Please tell me if it is.) Assuming there wasn't a formalism to prove a solution, there would need to be a large number of test-cases which returned correct results. Is there a list of such test cases for the subset-sum problem? Obviously this would have to include negative results (i.e. tests to see if the algorithm returns false positives). Can someone help me out with these questions, or point me to a better place to ask? I realize these are far-removed from game programming, even for the General Programming board... Thank you!

Share this post


Link to post
Share on other sites
I'll respond to the parts for which I have clear answers.
Quote:
Original post by EmrldDrgn
Are simpler cases of NP-complete problems still NP-complete?

There are many examples of NP-complete problems that can be restricted and stay NP-complete. For instance, SAT and 3SAT.

Quote:
For instance, if you restrict the subset-sum problem to the case of a set of positive integers summing to a positive integer, is it still NP-complete?

Yes, that would be another example.

Quote:
Assuming there wasn't a formalism to prove a solution, there would need to be a large number of test-cases which returned correct results. Is there a list of such test cases for the subset-sum problem? Obviously this would have to include negative results (i.e. tests to see if the algorithm returns false positives).

A finite list of sample tests would not prove anything.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
A finite list of sample tests would not prove anything.


Well, true, but in the absence of a formal way to prove algorithms correct, it would be better than nothing. Plus it would provide a nice "sanity check" for an algorithm at the very least - if it fails one of the tests, it obviously CAN'T be a correct solution. So it could DISprove something, which is progress of a sort.

Share this post


Link to post
Share on other sites
Quote:
Original post by EmrldDrgn
Assuming there wasn't a formalism to prove a solution, there would need to be a large number of test-cases which returned correct results. Is there a list of such test cases for the subset-sum problem? Obviously this would have to include negative results (i.e. tests to see if the algorithm returns false positives).


I'm very rusty on this kind of stuff.

But wouldn't generating these tests be equivalently complex problem? Or at very best, something like the dynamic programming solution, which trades off time for space, and space becomes the problem?

Share this post


Link to post
Share on other sites
Quote:
Original post by EmrldDrgn
Are simpler cases of NP-complete problems still NP-complete? For instance, if you restrict the subset-sum problem to the case of a set of positive integers summing to a positive integer, is it still NP-complete? Some web resources I've found (like this one) actually define the problem this way, but it seems to me to be not-the-same.

Restricting an algorithm can change it's complexity class.

If you were previously trying to answer problem A, but the restriction means you are now answering problem B, if A != B then you could easily have changed the complexity.
Quote:
Is there some kind of mathematical or computer-science formalism that would need to be used to prove that a proposed polynomial-time solution to an NP-complete problem was a) polynomial-time and b) actually solved the problem in all cases? It seems like there would need to be, but I don't know what it would be, especially since (if I remember correctly) someone (Turing?) proved that not all algorithms can be mathematically proven correct in all cases. (The previous statement could be completely wrong. Please tell me if it is.)
Yes, the simplest method is to see if the problem is known to be reducible to another problem. If you don't already know if the problem matches another known problem, you can generally look over the loops and exit states to figure it out.

There have been several proofs and theses showing that certain algorithms are unprovable ("independent"), and that others are unknowable under our current knowledge. Other problems can be proven to be uncomputable, others are intractable, and still others are undecidable.




Outside of academics and research, if you have to study the complexity of the algorithm then it will generally be too complex for the real world.


It is possible (and easy) to implement an algorithm that is more complex than the problem requires. If you have a particular algorithm for your problem, you may find that picking a different algorithm can meet the requirements under more favorable terms.

Quote:
Assuming there wasn't a formalism to prove a solution, there would need to be a large number of test-cases which returned correct results. Is there a list of such test cases for the subset-sum problem? Obviously this would have to include negative results (i.e. tests to see if the algorithm returns false positives).

If you are familiar with complexity, it is usually enough to just look at loop's exit conditions. Is it guaranteed to ever exit? Does it require an exhaustive search, or require evaluation of all combinations, or can it stop the first time a certain condition is met? If you know these things you may be able to identify the complexity without further effort.


If you must actually prove it mathematically, you will generally need to reduce the problem to another problem of known complexity. To prove the reduction you typically use induction [prove R(0), prove R(n+1)], breadth-first countability [given multiple infinite countable sets, the cross of those sets is countable], diagonalization [similar to breadth-first countability except using a diagonal set], and isomorphism [finding a set of operations that map your solution to another known problem]. You can also find counter-examples to prove that an algorithm is outside a particular complexity class if that helps narrow your search.



There is no set of constructive rules that will always auto-generate these proofs. That was something a lot of mathematicians wanted, but they managed to prove that such a system could not exist. [grin] Sometimes you can find or construct them easily, other times they are difficult or impossible to find.

Share this post


Link to post
Share on other sites
Hmm, interesting...
Quote:
Original post by frob
Restricting an algorithm can change it's complexity class.

If you were previously trying to answer problem A, but the restriction means you are now answering problem B, if A != B then you could easily have changed the complexity.

Yeah, this is what I figured to be generally true. What about the specific case I mentioned, subset-sum with a set of positive integers adding to a positive integer? Is that still NP-complete?

Quote:
If you are familiar with complexity, it is usually enough to just look at loop's exit conditions. Is it guaranteed to ever exit? Does it require an exhaustive search, or require evaluation of all combinations, or can it stop the first time a certain condition is met? If you know these things you may be able to identify the complexity without further effort.

If you must actually prove it mathematically, you will generally need to reduce the problem to another problem of known complexity. To prove the reduction you typically use induction [prove R(0), prove R(n+1)], breadth-first countability [given multiple infinite countable sets, the cross of those sets is countable], diagonalization [similar to breadth-first countability except using a diagonal set], and isomorphism [finding a set of operations that map your solution to another known problem]. You can also find counter-examples to prove that an algorithm is outside a particular complexity class if that helps narrow your search.

This is talking solely about proving complexities, right? If that is the case, is there a way to do something similar for results? For instance, if I claimed to have a subset-sum algorithm, and I could prove it ran in O(n^2), the truth of that would be irrelevant if I handed you a bubble sort.

Share this post


Link to post
Share on other sites
Quote:
Original post by EmrldDrgn
[...] What about the specific case I mentioned, subset-sum with a set of positive integers adding to a positive integer? Is that still NP-complete?

I already told you that it is. You can prove it by reducing the subset-sum problem to a polynomial number of similarly-sized instances of the positive-subset-sum problem.

Share this post


Link to post
Share on other sites
OK, thank you very much :). I have one more question... is the set whose subsets are examined in subset-sum a set in the mathematical sense, which cannot contain duplicate numbers (i.e. subsetsum({1, 1, 1}, 3) returns false)? Or is it (as some sites explain) a list, which can contain duplicates (the above returns true)?

Share this post


Link to post
Share on other sites
As I understand it, the problem considers a set in the mathematical sense for both inputs and outputs, or more specifically, that a solution either contains or does not contain each element in the input set. To use your example, the {1,1,1} input 'set' [which would be an invalid input if you consider the mathematical sense] would be viewed by the problem description as {a,b,c}, and a solution would consist of something like a+b+c = solution [3].

This is sort of where it's np-completeness argument stems from in the first place, and is the source of its reducability to SAT. Each input is either taken [true] or not taken [false]. If you consider the special cases where you have a small 'solution' value, you can execute this with a dynamic approach. But when the 'solution' value begins to require a considerable number of the input set elements, it blows up.

Yes, definately, both the 'positive and negative numbers summing to zero' version and the 'positive integers summing to an even larger positive integer' version are both NP, and the problem is generally stated to only include each of the input elements once, or not at all.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this