No such thing as a small change PerlMonks

### 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 ( #1031854=note: print w/replies, xml ) 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.
• Comment on Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable))

Replies are listed 'Best First'.
Re^6: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable))
by hdb (Monsignor) on May 03, 2013 at 11:17 UTC

Full agreement on my side. Just a couple of comments:

• The OP did add some comment to the thread today, so at least s/he is reading it.
• Providing a polynomial algorithm to one particular NP complete problem is proof for P=NP and the price is yours. Caveat is that most believe, but cannot prove, that P <> NP.
• Approximate solutions are of high value, no question! A large part of our economy runs on them.
• I have and had no intention to belittle your proposed solutions. Just the opposite: I learnt a lot from studying your code.
• Besides the practical application of solutions produced here in the monastery, a bit of pure science should be allowed as well. Even if only for the intellectual challenge and not for any practical use. These kind of discussions seem to have a tendency to drift away from the original question.

• The OP did add some comment to the thread today, so at least s/he is reading it.

I kept waiting, hoping for more than "TRUE". :(

• Providing a polynomial algorithm to one particular NP complete problem is proof for P=NP and the price is yours. Caveat is that most believe, but cannot prove, that P <> NP.

Is that so? Or could it just demonstrate that some things thought to be NP aren't?

But either way, a GA algorithm that finds a solution, most of the time would not qualify as proof of anything; and that's all I was trying to achieve. As I said in my post above, choroba's exhaustive solution is perfect if the OPs task deals with smallish sets; but if he needs to deal with larger, a different tack is required.

• Approximate solutions are of high value, no question! A large part of our economy runs on them.

Agreed.

• I have and had no intention to belittle your proposed solutions. Just the opposite: I learnt a lot from studying your code.

Polite and thank you. But I'm not quite sure what could be learnt from it, given it was both crude and incorrect.

• Besides the practical application of solutions produced here in the monastery, a bit of pure science should be allowed as well. Even if only for the intellectual challenge and not for any practical use. These kind of discussions seem to have a tendency to drift away from the original question.

Hm. You're right of course that it should be allowed, but I have my doubts as to either its utility or its entertainment value.

And beyond having another million in the bank, which is never a bad thing, I really wonder at the benefit to mankind of the "solving" (really just proving) of such a "problem"?

Take Will's proof of FLT. There were 200 accomplished mathematicians in the room at Princeton when he set out his first attempt at the proof. And it is reckoned by many that less than 1/4 of that heady group stood even the slightest chance of understanding even the notation he used. And of that subset, only 3 or 4 that were sufficiently accomplished to see its flaws.

And by some estimates, in the 10 years since, there are still less than the 200 people that were in that room that really understand the corrected proof he later gave. And to my knowledge (limited), there have been no practical benefits that have arisen from it.

That's not to say that there couldn't be something come up in the future; and certainly does not set me against pure science -- by pure scientists -- for its own sake.

I just wonder at the utility of such (often only half understood) academic discussion, by programmers, who are (mostly) amateurs in the field of mathematics, around the attempts to solve real world problems. From my 10 years around here, when such discussion comes up, it is usually in the context of attempting to dismiss the idea that individual proposed solutions have any merit; or to dismiss the problem as insoluble.

Neither of which are helpful given that, in the real world, even the most intractable of problems can always be approximated to sufficient accuracy to provide useful solutions. Even when they are not correct from a pure science viewpoint.

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.
Re^6: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable))
by LanX (Bishop) on May 03, 2013 at 19:31 UTC
too long didn't read all, but

> > 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.

Well not in this case!

A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for C, we could solve all problems in NP in polynomial time.

So finding an algorithm for the partition problem, proven to find a solution (or it's non-existence) in polynomial time (including for the worst case) means solving P vs NP!!!

> 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"!

Well, bad trained personnel!

Problem classes are classified by their worst case. But normally most cases can still be solved pretty fast with already well known algorithms.

In praxis stopping after a timeout for few remaining cases is acceptable.

##### Edit

Especially if they calculate an approximate solution.

In many cases something like (sum @part1 -sum @part2) < min @all is already sufficient.

Cheers Rolf

( addicted to the Perl Programming Language)

too long didn't read all

Shame you have such a limited attention span. Otherwise you might have bothered to read the whole of the sentences you quoted.

I draw your attention to: finding solutions to particular, restricted or bounded examples of particular NP problems

Well, bad trained personnel!

You'd know. YOU are one of them.

Especially if they calculate an approximate solution.

Again, if you could've maintained your attention span for the whole 45-50 seconds it would've taken you to read the entire post, you'd realise that all you doing it repeating what *I said* in my post.

Please don't respond further as I can't be bothered with having to repeat myself over and over.

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.
> Again, if you could've maintained your attention span for the whole 45-50 seconds it would've taken you to read the entire post, you'd realise that all you doing it repeating what *I said* in my post.

Apparently clearer and with less words.

I tried to read it again and gave up.

> > Well, bad trained personnel!

> You'd know. YOU are one of them.

hdb was pretty clear that you would win this contest, if your algorithm did what you are claimingı it does.

You denied it.

I don't enjoy discussing with your propaganda machine, but from a logical POV thats plain wrong!

Somebody needed to say it, no matter how many insults your piling on people with other opinions.

plonk

Cheers Rolf

( addicted to the Perl Programming Language)

Create A New User
Node Status?
node history
Node Type: note [id://1031854]
help
Chatterbox?
and !@monks...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2018-06-19 03:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (111 votes). Check out past polls.

Notices?