From: Lou Vanek <vanek@...>
Date: 2006-02-08T23:41:04+09:00
Subject: Re: [ANN] NP

Gregory Seidman wrote:

> On Wed, Feb 08, 2006 at 10:36:01PM +0900, Lou Vanek wrote:
> } If anybody else finds NP-complete problems interesting then you may want
> } to check out my new Ruby extension. You can find the extension, ext_np, at
> } http://rubyforge.org/frs/?group_id=835
> } 
> } The description follows in the README.
> } This extension is wicked fast.
> } 
> } -lv
> } 
> } ----------------------------------------------------------------------------
> } README.txt
> } 
> } This extension, 'NP,' is a module for the Ruby language. It includes four
> } optimized NP-complete algorithms:
> } 
> }     o    Multiple Knapsack 0-1
> }     o    Subset Sum
> }     o    Symmetric Subset Sum
> }     o    Satisfiability (SAT)
> 
> So does this mean there won't be any more Ruby Quizzes based on NP-complete
> problems? Please? I mean, if you've solved one, you've solved them all.
> 
> --Greg

The algorithms are fast, but still exponential. The knee in the curve,
however, is far off to the right compared to traditional branch-and-bound
algorithms. For small and medium-sized problems though, yes, if you can
discover a mapping from your problem to one of these four algorithms, your
problem is (quickly) solved.

-lv