Re: Re: (Golf) Minimizing the Bacon Number

[Masem]

in reply to Re: (Golf) Minimizing the Bacon Number
in thread (Golf) Minimizing the Bacon Number

This problem shouldn't be NP-complete. A well-rounded algorithm is going to be, I believe, O(N^2) or O(N^3). However, the golf solution will probably be NP.

---

Dr. Michael K. Neylon - [e-mail] || "You've left the lens cap of your mind on again, Pinky" - The Brain

[bobione]

Sorry to ask but my curiosity is too big...
What is NP (or NP-complete) ?
Thanks.

BobiOne KenoBi ;)

[MeowChow]

Here's one definition.

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

[jynx]

An NP problem is a programming problem that can only be solved by the theoretical nondeterministic Turing machine (NP stands for Nondeterministic Polynomial). An NP-Complete problem has the property that if you can find a polynomial running time solution to this problem than you can find a polynomial solution to all other NP problems as well. Unfortunately, that works both ways, if you prove that there is no polynomial solution to the problem than all other NP problems don't have a polynomial runtime as well.

For more information, look here.

Hope This Helps,
jynx

Update: D'oh! Beaten by MeowChow...

[koolade]

Search Google: NP-complete

Update: Didn't see the above posts...whoops.