From: Timothy Bennett <timothy.s.bennett@...>
Date: 2006-03-31T00:20:39+09:00
Subject: Re: [QUIZ] B & E (#72)

On Mar 29, 2006, at 11:37 PM, Ross Bamford wrote:
>
> I think this problem is basically the shortest common superstring
> problem:
>
> http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE209.HTM
>
> Which is basically how my solution (and I think yours too) approached
> it. The upshot is that it's easy to find a common superstring, and  
> even
> a reasonably short common superstring, but very difficult to find the
> _shortest_ or determine how long it would be (it's NP complete I
> think).

I definitely need to study more math and algorithms.  Yes, this does  
seem to be a variation on the shortest common superstring, and the  
sources I'm finding say that it is NP-complete.  Unfortunately, the  
existence of the stop digits seems to complicate matters somewhat.   
The most thorough discussion I've found online (so far, haven't  
looked very long yet) is a PDF discussing, of all things, the Pokemon  
trading card game: http://home.earthlink.net/~mstamp1/papers/poke.pdf

Nothing I've found so far discusses how one might predict the length  
of the shortest common superstring, though.  I feel, that for our  
rather narrow problem domain, that it should be possible.  Especially  
since the substrings in the more traditional superstring problems are  
random to some degree, while we know what all of our strings are.   
Hm, I'll have to think on this more.

Tim