Chapter Five
Classifying Problems into Complexity Classes
William Gasarch University of Maryland, Maryland, USA
Abstract
A fundamental problem in computer science is stated informally as: Given a problem, how hard is it? We measure hardness by looking at the following question: Given a set A what is the fastest algorithm to determine if “x ∈ A?” We measure the speed of an algorithm by how long it takes to run on inputs of length n, as a function of n. For example, sorting a list of length n can be done in roughly n log n steps.
Obtaining a fast algorithm is only half of the problem. Can you prove that there is no better algorithm? This is notoriously difficult; however, we can classify problems into complexity classes where those in the ...
