[mjcohen]

Depends what you mean by larger. The example that occurs to me is the priblem of determining whether or not an integer is prime. This can be done relatively quickly for numbers of the form 2^p-1 where p is prime, but would take much longer for a much smaller prime not of this form.

[Nevermark]

Those would be effectively different problems.

Adding the constraint of only needing to classify a particular form of prime will always result in an algorithm of equal or lesser complexity order.