Kolmogorov Techniques in Computational Complexity Theory

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii CHAPTER 1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 iHow Hard is this Problem?j . . . . . . . . . . . . . . . . . . . . 1 1.1.1 An introduction to computational complexity . . . . . . . 3 1.1.2 An introduction to Kolmogorov complexity . . . . . . . . 6 1.2 Overview of the contributions and previous work . . . . . . . . . 9 1.2.1 Self-reductions . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Extractors . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 Indistinguishability . . . . . . . . . . . . . . . . . . . . . . 10 1.2.4 Collaboration and publication status . . . . . . . . . . . . 11 2. PRELIMINARIES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1 Notational conventions . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Kolmogorov complexity . . . . . . ...