Computational Complexity

Thursday, February 10, 2005

 
Favorite Theorems: The Seminal Paper

Posted by Lance

Introduction

We should start off off my list of favorite theorems from the first decade of complexity with the seminal paper in complexity, the one that gives the field and this weblog its names.

Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society, 117 (1965), 285-306.

This paper formalizes the idea that we now all take as obvious that we should use Turing machines to determine complexity of complexity by measuring time as a function of the size of the input. Ever since the Hartmanis-Stearns paper we measure nearly every resource (time, space, random bits, circuit depth, etc.) as a function of the input size.

This paper also gives the first hierarchy of classes, showing that for nice functions t and u with t²(n)=o(u(n)) then there are problems solvable in time u(n) but not time t(n) on multitape Turing machines. Soon later Hennie and Stearns showed the same result if t(n) log t(n) = o(u(n)).

1:58 PM #

Comment Feeds: This Post All