Version: 0.3.38
Computational Complexity#
Now we have covered quite many concepts, algorithms, and data structures. What remains is to see how all that fits together. That is the purpose of Computational Complexity theory: Understand how computational problems and algorithms relate. This is the core of theoretical Computer Science and we will only introduce the very basic concepts, starting with regular expressions, and formal languages. From there, we will look at complexity classes, which categorize computational problems—not algorithms—in to groups like “feasible”, “hard”, etc. This explains the implications of the “P = NP” question, yet still open.