Because you can not add in one motion. It is impossible to be given numbers: 3,4,6 and add three to each in one motion. If this was possible NP complete problems would be simple. Without this criteria it is impossible to solve NP complete problems without exponential time.
The problem of NP complete problems are not suited to the computer. Another means of calculation would be better suited.
Name:
Anonymous2008-06-09 17:03
ITT people who haven't messed with NP complete problems enough
Yes my writing is mostly scribbles as it really isn't worth the time to explain them thoroughly and I am not filtering them at all. Also none of it really matters as it sheds no new light that isn't already known about NP-completeness.
From Wikipedia:
The complexity (difficulty of solution) of subset sum can be viewed as depending on two parameters, N, the number of decision variables, and P, the precision of the problem (stated as the number of binary place values that it takes to state the problem). (Note: here the letters N and P mean something different than what they mean in the NP class of problems.)
The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. Thus, the problem is most difficult if N and P are of the same order. It only becomes easy if either N or P becomes very small.
If N (the number of variables) is small, then an exhaustive search for the solution is practical. If P (the number of place values) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.
What is happening is that the problem becomes seemingly non-exponential when it is practical to count the entire solution space. There are two ways to count the solution space in the subset sum problem. One is to count the number of ways the variables can be combined. There are 2^N possible ways to combine the variables. However, with N = 10, there are only 1024 possible combinations to check. These can be counted easily with a branching search. The other way is to count all possible numerical values that the combinations can take. There are 2^P possible numerical sums. However, with P = 5 there are only 32 possible numerical values that the combinations can take. These can be counted easily with a dynamic programming algorithm. When N = P and both are large, then there is no aspect of the solution space that can be counted easily.