P is for Practical PerlMonks

### 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 ( #1031861=note: print w/replies, xml ) Need Help??

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.

• Comment on Re^6: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable))

Replies are listed 'Best First'.
Re^7: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable))
by BrowserUk (Pope) on May 04, 2013 at 07:10 UTC
• 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.

Create A New User
Node Status?
node history
Node Type: note [id://1031861]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2017-08-22 08:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (332 votes). Check out past polls.

Notices?