Syntactic Confectionery Delight  
PerlMonks 
Re: Perl regular expressions vs. RL, CFL, CSLby JadeNB (Chaplain) 
on Dec 14, 2009 at 17:08 UTC ( #812749=note: print w/ replies, xml )  Need Help?? 
NPcompleteness is a property of an algorithm. It implies that no algorithm is known to solve the problem in polynomial time. I think that this may be a little misleading. Right now (as 6 years ago), NPcompleteness of a problem means that no polynomialtime algorithm is known, but that statement may eventually become false ^{*}. Maybe it's better to say “Computer scientists believe that, if a problem is NPcomplete, then there is no polynomialtime algorithm to solve it”? Also, I'm not sure that it's fair to say that NPcompleteness of a problem means that the timecomplexity of the problem grows exponentially in the input. Again, we think that NPcompleteness correlates with exponential timecomplexity, but that could change ^{*}. For that matter, can't NPcomplete problems have superexponential complexity (like 2^(n^2))—or are you using ‘exponential’ in the generic sense of ‘fastergrowing than polynomial’? ^{*} Although we all know that it won't really. :)
In Section
Seekers of Perl Wisdom

