Computer Science › Section M · Theory of computation › Topic M.5
Complexity of problems: P and NP
Some problems can be solved in principle but would take longer than the age of the universe. Complexity theory sorts solvable problems by the time they need, and its central question, whether P equals NP, is one of the most famous unsolved problems in mathematics.
In this topic
- Solvable is not the same as practical
- Polynomial time and the class P
- Worked example: polynomial against exponential
- Problems outside P
- The class NP
- Worked example: checking versus finding
- Reductions
- Worked example: applying the reduction
- NP-complete problems
- P versus NP: an open question
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…