Communications of the ACM
Juris Hartmanis, 1928-2022
A 1977 paper by Hartmanis and Leonard Berman introduced the still-unsolved Berman–Hartmanis conjecture that all NP-complete languages are polynomial-time isomorphic.
Credit: ACM
Juris Hartmanis, co-recipient of the 1993 ACM A. M. Turing Award and a professor in Cornell University’s computer science department since 1965, passed away on Friday at the age of 94.
The Turing Award was bestowed on Hartmanis and Richard Stearns for their paper “On the Computational Complexity of Algorithms.”
Dick Karp, a computational theorist at the University of California, Berkeley, said the paper "marks the beginning of the modern era of complexity theory. Using the Turing machine as their model of an abstract computer, [Hartmanis and Stearns] provided a precise definition of the 'complexity class' consisting of all problems solvable in a number of steps bounded by some given function of the input length {n}. Adapting the diagonalization technique that Turing had used to prove the undecidability of the Halting Problem, they proved many interesting results about the structure of complexity classes."
From Gödel’s Lost Letter and P=NP
View Full Article
Abstracts Copyright © 2022 SmithBucklin, Washington, DC, USA
No entries found