X-Received: by 10.182.128.166 with SMTP id np6mr10338812obb.16.1401573586618; Sat, 31 May 2014 14:59:46 -0700 (PDT) X-Received: by 10.50.120.1 with SMTP id ky1mr131608igb.7.1401573586482; Sat, 31 May 2014 14:59:46 -0700 (PDT) Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!c1no21642957igq.0!news-out.google.com!qf4ni17772igc.0!nntp.google.com!c1no21642952igq.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.programming.contests Date: Sat, 31 May 2014 14:59:45 -0700 (PDT) In-Reply-To: <3vgojd$88q@lyra.csx.cam.ac.uk> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=50.20.186.81; posting-account=myC5egoAAAC_1N03kD3HpMOjlKv7GUyk NNTP-Posting-Host: 50.20.186.81 References: <3vg23j$g70@miso.wwa.com> <3vgh0p$jqi@vixen.cso.uiuc.edu> <3vgojd$88q@lyra.csx.cam.ac.uk> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: A fun little problem From: princeofyourpeople@gmail.com Injection-Date: Sat, 31 May 2014 21:59:46 +0000 Content-Type: text/plain; charset=ISO-8859-1 Xref: csiph.com comp.programming.contests:38 On Sunday, July 30, 1995 12:00:00 AM UTC-7, Paul Hankin wrote: > In article <3vgh0p$jqi@vixen.cso.uiuc.edu>, > James Irl Waldby wrote: > >sigfried@miso.wwa.com (Sigfried Gold) writes: > > > >>Ok, here's a little challenge, not too hard to do for fun, but not > >>idiotically easy, at least not for me. This seems like a contrived > >>problem, but actually it came up in real life. > > > >>The problem is: write program that finds all the combinations of > >>a set of whole numbers that add up to a larger number. > > > >If you have a program to solve this problem, then it can solve the > >"PARTITION" problem, a well-known NP-complete problem. (See page 47 > >of M. R. Garey & D. S. Johnson, "Computers and Intractability".) > >At the moment there is no known solution for PARTITION that runs > >in polynomial time. > > > [...snip...] > > > >NP-completeness of a problem implies that for any solution method P, and > >any polynomial expression t(s) [where s = problem size in some reasonable > >metric] there is a data set A such that P takes more time than t(s(A)) > >to solve with A. In other words, you might have a heuristic approach that > >works fast for many problems, but there are data sets it is going to take > >a long time to solve. So it would be a big breakthrough if you could > >prove you have a good solution! > > > > NP completeness says no such thing. A problem is NP complete if the > problem is NP and the existence of an algorithm which solves the > problem in polynomial time implies the existence of an algorithm for > solving (say) the k-clique problem in polynomial time. > However, I still agree that a good solution would be a big breakthrough, > as it would prove P=NP. > > [more snipped] > > > >>Also, writing a short program is not nearly as desireable for this > >>as writing a program that's easy to read and understand. Looking > >>back at my solution to this, it's plenty short enough, but it could > >>take days now to figure out what I was trying to do. > > I can't see the point in a programming competition which says `write this > trivial program in a sound way using all the principles of software > engineering that you can think of' because (a) most sensible programming > techniques are a matter of following guidelines, (b) it's impossible > to judge whose program is best, as different people have different ideas > about style and (c) it isn't very interesting IMO. Writing the shortest > bit of code you can think up is a _much_ better competetion as it requires > serious ingenuity to compress the code to its minimal form. > I wouldn't dispute the fact that writing terse code is not as > desirable as clear code for most purposes, but when it comes to > contests, I claim a short-is-best rule makes for more interest. > > -- Paul Hankin A big giant solution