|
The student is able to
- classify problems in the various complexity classes
- provide proofs of the main theorems
- perform constructions similoar to the ones discussed during the course
|
|
|
Complexity theory is a field on the border of mathematics and computer science, where computational problems are classified according to the resources (such as computation time and space) that are needed to solve them. This leads to a number of fundamental complexity classes such as P, NP, PSPACE and many others. These classes serve as benchmarks for the difficulty of computational problems, and have numerous applications in mathematics as well as in other fields. This area is also the home of one of the most fundamental unsolved problems in mathematics, namely the question whether the classes P and NP are equal or not.
|
|
|
| Mathematical maturity commensurate with master's level, as well as a first course in mathematical logic, say as in the book J. van Oosten and I. Moerdijk, Sets, Models, and Proofs. In particular, acquaintance with propositional logic and first order predicate logic is required. |
|
|
|