[clug] OT meta-regex question

David Price david.price at anu.edu.au
Tue Feb 3 06:17:28 GMT 2004


On Tue, Feb 03, 2004 at 04:48:30PM +1100, David Gibson wrote:
> Definitely worth looking at that - this looks like a pretty deep
> problem to me, not one that would be obvious quickly.  If I hadn't
> seen that page purporting to have an implementation of intersection I
> wouldn't have been surprised if the problem turned out to be
> NP-complete.

NP-complete often isn't a lost cause.  Many problems are classified as
NP-complete when only certain diabolical cases behave badly.  For
example, SAT problems that are either over constrained (highly likely
to not have a solution), or under constrained (has many solutions) are
both fairly quick to solve.  It's just the critically constrained
problems (the ones in the middle) that are difficult to solve.

Most experimentation done in computer science these days (at least
from my perspective) is on algorithms that are at least NP-complete,
if not PSPACE-complete or one of the other nasty classes.

I was at a talk today where someone mentioned that the complexity of a
problem they were dealing with was "non-elementary" - 2^2^2^2...2 (n
times).  Now that would blow up nastily :)

David


More information about the linux mailing list