CHAPTER 5
COMPUTATIONAL COMPLEXITY
What do we mean by saying “this problem, x ∈ A, has no algorithmic solution”? And why is it that some problems do not have such solutions? How can we classify (compare) such undecidable problems? These are the fundamental questions of computability theory that we studied in Chapter 2.
Among the problems x ∈ A that do have algorithmic solutions (decidable or solvable problems), why is it that some require enormous computational resources toward obtaining the answer? And how can we classify decidable problems according to their demand on computational resources? This is the domain of computational complexity, or just complexity, theory. This chapter discusses a few topics in complexity theory.
Get Theory of Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
