Bernhard Haeupler

Introduction to Complexity Theory

Abstract

This paper is a short repetition of the basic topics in complexity theory. It is not intended to be a complete step by step introduction for beginners but addresses to readers who want to refresh their knowledge efficiently. We start with the definition of the standard
(non)deterministic time and space bounded complexity classes. Next the important concept of reduction and completeness is discussed intensively. After a short excursion on Boolean circuits several completeness results in P, NP and PSPACE strengthen the routine of these methods and give a broad base for further hardness results. Besides that we have a look at optimization problems in PNP and classify these problems within the polynomial hierarchy. The polynomial hierarchy is then characterized through the notion of certificates, which make it more comfortable and intuitive to handle. With this characterization we close with some facts about PH collapses.