Complexity Theory Basics: NP and NL

摘要

We introduce basic concepts and results in computational complexity as background for some of the articles in this volume. Our focus is on the complexity classes nondeterministic polynomial time (NP) and nondeterministic logarithmic space (NL). The presentation is aimed at computer science students at a senior undergraduate level, and assumes some familiarity with algorithm design and theory of computation. The material is covered at a fairly brisk pace. Several results and proof details are incorporated in exercises which the reader is urged to solve or look up in textbooks such as [BDG88, Pap94, AB09].