Groups | Search | Server Info | Login | Register

Groups > comp.programming.contests > #38

Re: A fun little problem

Show all headers | View raw

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 <jw13032@glhpx11.cen.uiuc.edu> 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

Back to comp.programming.contests | Previous | Next | Find similar

Thread

Re: A fun little problem princeofyourpeople@gmail.com - 2014-05-31 14:59 -0700

csiph-web