
So I think there's two things that are true here. The first one is polynomial time,

because we're trying to do preprocessing for problems that normally require exponential time.

So if we don't have this requirement here, you could use preprocessing to already solve the problem,

because then you would have exponential time. And that really wouldn't make any sense.

Of course, in practice it could make sense to have certain exponential time preprocessing algorithms where,

for example, the base of the exponent is much smaller than of the general algorithm.

But actually I've never seen that done. And right now, for us, polynomial time is a good requirement to have.

Speeding up worsecase running time is, in my opinion, not a requirement for preprocessing.

Of course, you would like to get a speedup, but on the other hand, as you've seen, the preprocessing rules are very simple.

So, we might always encounter instances where preprocessing does not apply.

But that doesn't mean we shouldn't do it. Preprocessing runs in polynomial time, so it's easy to do.

So we should just hope that preprocessing helps us, but not make it a requirement.

And finally, that is of course very important. Preprocessing must not affect the solution that we get in the end.

If we have a decision problem where the answer is yes or no, after preprocessing, we want the answer to be the same, of course.

And the same is for optimization problems. If the answer is 10, 11 or 12, then after preprocessing,

the answer should remain 10, 11 or 12. Because otherwise, preprocessing would actually alter the problem,

and it would alter the solution to that problem, which of course is something we do not want.