tag:blogger.com,1999:blog-3722233.post1587140923174173168..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: Juris Hartmanis passed away on July 29 at the age of 94Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-70731917322110056952022-09-30T16:01:04.249-05:002022-09-30T16:01:04.249-05:00R.I.P , Juris Hartmanis .R.I.P , Juris Hartmanis .Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31037924722562667682022-08-02T02:56:39.150-05:002022-08-02T02:56:39.150-05:00R.I.P , Juris HartmanisR.I.P , Juris Hartmanisslimhttps://www.blogger.com/profile/11323935792102948064noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12014789029454952622022-08-01T09:31:23.498-05:002022-08-01T09:31:23.498-05:00People were also interested in algebraic formulati...People were also interested in algebraic formulations--Juris has a book (with Stearns) on the Algebraic Structure Theory of Sequential Machines. (cf Kron-Rhodes decomposition, Schutzenberger Thm on torsion-free semigroups for work in this direction). Subrecursive hierarchies (Grzegorczyk, Ritchie, etc.) were an attempt to relate "running time complexity" to structure.<br />People also were interested in "complexity" as minimum size (e.g. minimum size universal Turing machines). <br />The idea of counting number of steps to measure complexity does not start with the Hartmanis-Stearns paper--von Neuman already proved operation count bounds for the ENIAC. Edmonds advocated for the distinction between P and NP, as did Cobham.<br />The set of Hartmanis et al papers was amazing because it suddenly made things clear, mathematical, and, in the best of this meaning -- easy. It changed the way we look at things.Janos Simonhttps://people.cs.uchicago.edu/~simon/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48516635960811501702022-08-01T05:12:19.335-05:002022-08-01T05:12:19.335-05:00People also tried to bring in ‘algebraic’ formalis...People also tried to bring in ‘algebraic’ formalisms to study and to synthesize circuits and automata. Juris had a book with Stearns on the algebraic structure theory of sequential machines. (cf. Krohn-Rhoades theory, Schutzenberger’s theorem torsion-free semigroups). There was some research in ‘simplicity/easiness’ as complexity—for example size of smallest universal Turing machine.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46373662527318816392022-07-31T02:15:53.790-05:002022-07-31T02:15:53.790-05:00The wiki entry is probably one of the very few one...The wiki entry is probably one of the very few ones that hasn't changed in the advent of these news, from 'is' to 'was'.<br />Usually you seem change the second news is announced.<br /><br />> https://en.wikipedia.org/wiki/Juris_Hartmanis <br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41903587320582583322022-07-30T13:42:14.579-05:002022-07-30T13:42:14.579-05:00Good question. I think the following is true but w...Good question. I think the following is true but would be happy if someone corrects or modifies:<br />People in Logic thought mostly in terms of DECIDABLE/UNDEC<br />People in Enginnering thought FAST/SLOW. <br />Hartmanis-Stearns and Knuth helped to bridge that gap and bring rigor to the FAST/SLOW distinction.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39921247459408623592022-07-30T12:08:57.811-05:002022-07-30T12:08:57.811-05:00> Before the Hartmanis-Stearns paper this was n...> Before the Hartmanis-Stearns paper this was not how people thought of things<br /><br />How did people think of things back then?David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.com