ABSTRACT
Computational complexity theory, or in other words, the theory of tractability and intractability, is defined in terms of limit behavior. A typical question of computational complexity theory is of the form: As the size of the input increases, how do the running time and memory requirements of the algorithm change? Therefore, computational complexity theory, among other things, investigates the scalability of computational problems and algorithms, i.e. it measures the rate of increase in computational resources required as a problem grows (see, e.g., Arora and Barak, 2009). The implicit assumption here is that the size of the problem is unbounded. For example, models can be of any finite size, formulas can contain any number of distinct variables, and so on. 1
