Страны: Juris Hartmanis - Латвия, США; Richard E. Stearns - США

Образование: Juris Hartmanis - Доктор философии в области математики, Калифорнийский технологический университет, 1955

Richard E. Stearns - Доктор философии в области математики, Принстонский университет, 1961

О лауреатах

С 1958 года Hartmanis и Stearns работали в исследовательской лаборатории General Electric. Они заинтересовались тем, сколько времени и памяти требуется для выполнения разных вычислений – областью, которую они назвали вычислительной сложностью. Они определяли разные классы вычислений в зависимости от того, сколько потребуется вычислить и/или требуемого объема памяти, что является мерой их сложности. Их совместная работа 1965 года (“Classification of Computations by Time and Memory Requirements”) заинтересовала ученых, предлагая рассматривать сложность таким же образом. В отличие от других подходов к теории сложности, Hartmanis и Stearns основывали свой анализ на измерении ресурсов, используемых алгоритмами при работе на определенных машинах. Чтобы иметь некоторую общность, они использовали машину Тьюринга в качестве базовой модели. Они были удивлены, обнаружив ряд важных теорем, связанных с анализом сложности. Они представили базовую концепцию, которую назвали классом сложности вычислений. Неофициально класс представляет все вычисления, которые могут быть выполнены с использованием заданного количества ресурсов. Их работа по основам теории сложности сыграла важную роль в создании информатики как формальной дисциплины, отличной от математики, физики и электротехники.

Ключевые слова: Computational Complexity Theory

Краткая библиография

1.	Hartmanis, J. and Stearns, R.E., Algebraic Structure Theory of Sequential Machines, Prentice-Hall, 1966.
2.	Hartmanis, J. and Stearns, R.E., “On the Computational Complexity of Algorithms,” Transactions of the American Mathematical Society, Vol. 117, Num. 5, May 1965, pp. 285-306. Статья, за которую Hartmanis и Stearns получили премию Тьюринга
3.	Stearns, R.E., J. Hartmanis and P.M. Lewis, “Hierarchies of Memory Limited Computations,” Proceedings of the 6th Annual Symposium On Switching Circuit Theory & Logical Design, Oct. 1965. Эта статья расширяет понятие вычислительной сложности для ограниченных пространств.