You may be right... I know that it's been shown that NP-Complete problems can be reduced (in P time) to a Perl regex match. But I don't think the proofs I've seen looked at .* vs. .*?. The constructions used backreferences.