How efficiently can problems be solved? What resource limits (time, memory) are required?
Computational complexity theory studies not just whether a problem can be solved, but how efficiently it can be solved. It classifies problems based on the resources required to solve them.
Two major aspects are considered:
- Time complexity - how many steps a computation takes
- Space complexity - how much memory is required
Problems are grouped into complexity classes (P, NP, PSPACE, etc.) based on resource requirements. The famous P vs NP question asks whether problems whose solutions can be verified quickly can also be solved quickly.
- Studies efficiency of computation
- Considers both time and space resources
- Classifies problems into complexity classes
- Uses Big O notation for asymptotic analysis
- P vs NP is a major open problem and Millennium Prize Problem
- Built from: Time Complexity, Space Complexity, Big O Notation
- Builds into: P vs NP Problem, NP-Complete
- Related: Computability Theory, Algorithm, Model of Computation
- A problem being “hard” doesn’t mean it’s impossible—just that it requires lots of resources
- Polynomial vs exponential time is a crucial distinction in practice
Complexity theory guides algorithm design and informs which problems are tractable in practice. The P vs NP problem is one of the most important open questions in computer science.