By Alan L. Selman (auth.), Alan L. Selman (eds.)

ISBN-10: 1461244781

ISBN-13: 9781461244783

ISBN-10: 1461287936

ISBN-13: 9781461287933

In 1965 Juris Hartmanis and Richard E. Stearns released a paper "On the Computational Complexity of Algorithms". the sphere of complexity idea takes its identify from this seminal paper and lots of of the key options and problems with complexity concept have been brought by way of Hartmanis in next paintings. In honor of the contribution of Juris Hartmanis to the sphere of complexity thought, a unique consultation of invited talks via Richard E. Stearns, Allan Borodin and Paul younger was once held on the 3rd annual assembly of the constitution in Complexity convention, and the 1st 3 chapters of this e-book are the ultimate models of those talks. They remember highbrow developments in Hartmanis' contributions. All yet one of many rest of the chapters during this quantity originated as a presentation at one of many contemporary conferences of the constitution in Complexity idea convention and seemed in initial shape within the convention complaints. In all, those expositions shape an exceptional description of a lot of up to date complexity theory.

Show description

Read Online or Download Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988 PDF

Similar theory books

The Evolutionist Economics of Leon Walras - download pdf or read online

Walrasian economics, and by means of extension Walras, has develop into a synonym for narrowly mechanistic methods to the topic. The Evolutionist Economics of Leon Walras even if, demonstrates that this trust is the results of a studying of Walras that is at top very partial. Albert Jolink exhibits that Walras' paintings had powerful evolutionary features and that Walras had a broader social imaginative and prescient than a few of the economists who've taken up his identify.

Read e-book online The Theory of Subnormal Operators (includes errata) PDF

"In a undeniable experience, subnormal operators have been brought too quickly as the idea of functionality algebras and rational approximation was once additionally in its infancy and will now not be correctly used to ascertain this type of operators. The development within the idea of subnormal operators that has take place over the last numerous years grew out of employing the result of rational approximation.

Flexible Shells: Theory and Applications - download pdf or read online

Euromech-Colloquium Nr. a hundred sixty five The shell-theory improvement has replaced its emphasis over the last 20 years. Nonlinear difficulties became its major cause. however the research was once until eventually lately predominantly dedicated to shells designed for energy and stiffness. Nonlinearity is the following proper to buckling, to intensively differ capable pressure states.

Theory of Symmetric Lattices by Prof. Dr. Fumitomo Maeda, Prof. Dr. Shûichirô Maeda (auth.) PDF

Of significant value during this publication is the concept that of modularity in lattices. A lattice is related to be modular if each pair of its components is a modular pair. The houses of modular lattices were conscientiously investigated by way of a number of mathematicians, together with 1. von Neumann who brought the $64000 research of constant geometry.

Extra info for Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988

Sample text

Szymanski. Succinctness of descriptions of unambiguous context-free languages. SIAM J. , 6:547553, 1977. [JH68] J. Hartmanis and H. Shank. On the recognition of primes by automata. JACM, 15(3):382-389, July 1968. [JH69] J. Hartmanis and H. Shank. Two memory bounds for the recognition of primes by automata. Mathematical Systems Theory, 3(2):125-129, 1969. [JHa68] J. Hartmanis. Tape reversal bounded turing machine computations. JCSS, 2(2):117-135, August 1968. 26 Allan Borodin [JHa78] J. Hartmanis.

3rd Annual ACM Symposium on Theory of Computing, pages 151-158, May 1971. [TJ79] T. Baker and J. Hartmanis. Succinctness, verifiability and determinism in representations of polynomial-time languages. In Pmc. 20th IEEE Found. of Comput. , pages 392-396, 1979. [TJR75] T. Baker, J. Gill, and R. Solovay. NP question. SIAM J. , 431-442, 1975. [VL76] V. Pratt and L. Stockmeyer. A characterization of the power of vector machines. J. Comput. , 12:198-221, 1976. 3 Juris Hartmanis: Fundamental Contributions to Isomorphism Problems Paul Young l ABSTRACT In this paper we survey Juris Hartmanis' contributions to isomorphism problems.

18:444475, 1971. [JJ74] J. Hartmanis and J. Simon. On the power of multiplication on random access machines. In Proc. IEEE 15th Symp. on Switching and Automata Theory, pages 13-23, October 1974. [JSi79] J. Simon. Division is good. In 20th Annual Symposium on Foundations of Computer Science, pages 411-420, October 1979. [KGo36] K. Godel. Uber die lange von beweisen. Ergebnisse eines mathematischen Kolloquiuns, 7:23-24, H136. [LGo82] L. Goldschlager. Synchronous parallel computation. Comput. , 29(4):1073-1086, 1982.

Download PDF sample

Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988 by Alan L. Selman (auth.), Alan L. Selman (eds.)


by Charles
4.3

Rated 4.02 of 5 – based on 42 votes