Computational Complexity - Bachelor's and Master's Theses
Marc Meier: Complexity of Search Problems and Nash Equilibria
Bachelor's Thesis, 2007.
Advisor: Prof. Dr. Markus Bläser
This work describes some of the latest important results in complexity theory. It is intended to show a computer scientist with some knowledge about common complexity classes like NP which other classes within NP can be defined by rather simple Lemmata such as "Every directed acyclic graph has a sink". The proofs of the PPAD-completeness of two famous problems are worked out in detail. The results in this work are taken from numerous papers and the intention is to give a good structured overview over the field, which is recently influenced by computer scientists, as well as, game theoreticians and economists.