From: Ken Bloom <kbloom@...>
Date: 2006-10-13T00:25:10+09:00
Subject: Re: [QUIZ] Posix Pangrams (#97)

On Thu, 12 Oct 2006 17:06:26 +0900, Martin Coxall wrote:

>> I suspect that the other optimization problem here may also be NP- 
>> Hard.
>> I'm not sure (in all of the 5 minutes that I'm writing this post)  
>> how to do
>> a simple reduction to that problem though.
> 
> True, but in this case the set to cover was small enough to make it  
> computationally feasible without having to rewrite it in Fortran. Phew.
> 
> Martin

There's also the matter of program structure. When dealing with an
NP-Hard problem, you know that any solution geared to do a heuristic
search quickly is not guaranteed to find the minimum.

And if you do naive searches of the entire solution space, the
number of POSIX utilities involved here is not all that trivial.  

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
I've added a signing subkey to my GPG key. Please update your keyring.