The complexity theory companion (Q5925718)

The book is intended for readers who seek an accessible, algorithmically oriented research-centered, up-to-date guide to several interesting techniques of computational complexity. In contrast to the organization of other books, each chapter of this book focuses on one particular technique in complexity theory. The technique is explained and the results achieved by it and its applications are presented. Each chapter is provided with bibliographic notes and a part containing open issues. The book is divided into the following chapters: 1. The self-reducibility technique; 2. The one-way function technique; 3. The tournament divide and conquer technique; 4. The isolation technique; 5. The witness reduction technique; 6. The polynomial interpolation technique; 7. The nonsolvable group technique; 8. The random restriction technique; 9. The polynomial technique. The book contains two appendices, the first presenting a concise overview on complexity classes, the second one on reductions. The book present a survey on a great variety of recent interesting techniques in complexity. It falls well into the long line of surveys or surveys-like monographs emphasizing the special field of computational complexity starting with Wagner's and Wechsung's monograph of the same name (Zbl 0584.68062).