|Perl Monk, Perl Meditation|
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable))by BrowserUk (Pope)
|on May 03, 2013 at 10:35 UTC||Need Help??|
And if kcott or BrowserUK manage to fix their programs, there is a $1,000,000 price on it:
No. Those prizes -- and in particular, the P v NP prize -- are not up for grabs for finding solutions to particular, restricted or bounded examples of particular NP problems. The prize is for proving that there is a whole class of problems for which there are no solutions. Quite a different matter indeed.
Despite that the OPs problem is fairly loosely stated, it does contain the relaxation of sufficient constraints -- specifically, Subset size does not matter -- that it removes the need to find either 'all solutions' or 'the optimal solution'; and that means that the problem ceases to to be "NP-complete".
And that brings us to a theme I've seen repeated many times in many places over my career, and frequently revisited here at the monastery.The scenario goes like this: a requirement is identified as desirable. Upon analysis, the code required to implement that requirement is identified as being some variation upon one or more of the classical NP-Complete problems; and the CS majors and half-well-reads in the room will throw their collective hands up saying, "It can't be done"!
But, on the basis of ever fading memory and usually reliable gut feel, I'd estimate that 8 out of 10 occasions, there is scope within that "some variation upon", to allow a 'good enough' solution to be found and implemented. Often all that is required is to remove the constraint that a perfect solution must be found every time.
Take for example the bin-packing/sheet cutting problem. On the basis of strictly correct theory, businesses who's basic operating models equate to one or the other variations of this classical problem shouldn't be able to operate; and yet we have glass-cutting services and dress makers operating in every city and small town; and the entire modern world economy would be impossible without that cargo planes and container ships and freight trains and white van men went about their daily business.
Once you factor time into the equations and realise that it isn't necessary to find perfect or optimal solutions -- that a container with a little empty space; or few offcuts from each 7' x 10' sheet are acceptable within the operating margins of the business model -- then a whole raft of NP-complete "impossible" problems cease to be so.
Indeed, there is a whole field (actually several whole fields), of computer science dedicated to finding good enough solutions to intractable problems. Namely Genetic Algorithms and its many offshoots. But, as with all heuristical algorithms, you need to know where the constraints can be relaxed; or the costs not exceeded to apply them. Ie. For the OPs purpose, can an exact balance of sums be overridden by a time constraint?
As is so often the case when these problems come up, the original description is so devoid of detail, it is impossible to reach conclusions about constraints might be relaxed in order to achieve a 'good enough' solution. My tactic in these situations is to post a naive -- ie. known imperfect -- solution and then wait for the OP to come back and explain why it is not good enough.
It is inherent in the OPs specification that not all sets are solvable -- sets with odd totals have no integer bipartition; sets like 6,4,4,4,4,4 cannot be equally partitioned -- so the OPs purpose has to accommodate these possibilities. And if his procedures and processes can accommodate the impossible conditions; who's to say that they couldn't also accommodate a slightly imperfect solution, even when a perfect solution might be possible?
Only the OP. But, as is also often the case when these problems come up, s/he has chosen not to involve themselves further. Which is a shame, because reaching a near equal partition can be done very quickly by several of the posted attempts; and adding a time-constrained, GA giggle to that would probably be able to refine that to complete equality in 95%+ cases with a few minutes of CPU.
But who is going to be bothered to expend such development energies when the OP doesn't seem to be interested any longer.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.