It is interesting to point out that for these complexity classes, an increase of a constant factor on the time or the space bounds does not change the complexity classes. The reason is that a TM with a larger alphabet set and a larger set of states can simulate, in one move, a constant number of moves of a TM with a smaller alphabet set and a smaller number of states. We only show these properties for deterministic complexity classes.

Proposition 1.12


Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.