Complexity Theory Retrospective

Juris Hartmanis is a pioneer of complexity theory. This Festschrift recalls his work and reviews the current state of the theory.

Inhalt
0 Introduction.- 1 Juris Hartmanis: The Beginnings of Computational Complexity.- 2 Juris Hartmanis: Building a DepartmentBuilding a Discipline.- 3 Juris Hartmanis: Fundamental Contributions to Isomorphism Problems.- 4 Describing Graphs: A First-Order Approach to Graph Canonization.- 5 Self-Reducibility: Effects of Internal Structure on Computational Complexity.- 6 The Structure of Complete Degrees.- 7 Applications of Kolmogorov Complexity in the Theory of Computation.- 8 The Power of Counting.