Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




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.