Alan L. Selman – författare

Complexity theory has been a flourishing area of research in the last ten years and currently provides one of the most active subjects for future research problems in computer science. This volume provides a survey of the subject in the form of a collection of articles written by experts that to- gether provide a comprehensive guide to research. The editors' aim has been to provide an accessible description of the current state of complexity theory,and to demonstrate the breadth of techniques and results that make the subject exciting. Thus, papers run the gamut from sublogarithmic space to exponential time and from new combinatorial techniques to interactive proof systems. As a result, researchers in computer science will find this an excellent starting point for study in the subject and a useful source of the key results known.

In 1965 Juris Hartmanis and Richard E. Stearns published a paper "On the Computational Complexity of Algorithms". The field of complexity theory takes its name from this seminal paper and many of the major concepts and issues of complexity theory were introduced by Hartmanis in subsequent work. In honor of the contribution of Juris Hartmanis to the field of complexity theory, a special session of invited talks by Richard E. Stearns, Allan Borodin and Paul Young was held at the third annual meeting of the Structure in Complexity conference, and the first three chapters of this book are the final versions of these talks. They recall intellectual and professional trends in Hartmanis' contributions. All but one of the remainder of the chapters in this volume originated as a presentation at one of the recent meetings of the Structure in Complexity Theory Conference and appeared in preliminary form in the conference proceedings. In all, these expositions form an excellent description of much of contemporary complexity theory.

In 1965 Juris Hartmanis and Richard E. Stearns published a paper "On the Computational Complexity of Algorithms". The field of complexity theory takes its name from this seminal paper and many of the major concepts and issues of complexity theory were introduced by Hartmanis in subsequent work. In honor of the contribution of Juris Hartmanis to the field of complexity theory, a special session of invited talks by Richard E. Stearns, Allan Borodin and Paul Young was held at the third annual meeting of the Structure in Complexity conference, and the first three chapters of this book are the final versions of these talks. They recall intellectual and professional trends in Hartmanis'' contributions. All but one of the remainder of the chapters in this volume originated as a presentation at one of the recent meetings of the Structure in Complexity Theory Conference and appeared in preliminary form in the conference proceedings. In all, these expositions form an excellent description of much of contemporary complexity theory.

Readers of Complexity Theory Retrospective (published by Springer-Verlag in 1990) will remember that the collection consisted primarily of articles that first ap­ peared in preliminary form at one of the meetings of the Annual IEEE Conference on Structure in Complexity Theory. In particular, Complexity Theory Retrospective contained final versions of high-quality technical expository presentations, includ­ ing talks that honored Juris Hartmanis on the occasion of his sixtieth birthday. We began planning for the current collection some months before the scheduled meeting in 1994 of the Tenth Annual IEEE Conference on Structure in Complexity Theory. As with the original volume, several of the papers in this book originated as presentations at one of the meetings of the Structure in Complexity Theory con­ ference. We are pleased to provide this forum for final, polished versions of these papers. As it turns out, 1994 was a watershed year for the Structures conference, for at this meeting the conference attendees voted to change the conference name to its current name, the Annual IEEE Conference on Computational Complex­ ity. In voting to remove the expression "Structure in," the conferees recognized the recent explosion of techniques and results in computational complexity, and expressed concern that the original conference name might not accurately reflect the current status. We approached this volume in the same spirit.

In 1965 Juris Hartmanis and Richard E. Stearns published a paper "On the Computational Complexity of Algorithms". The field of complexity theory takes its name from this seminal paper and many of the major concepts and issues of complexity theory were introduced by Hartmanis in subsequent work. In honor of the contribution of Juris Hartmanis to the field of complexity theory, a special session of invited talks by Richard E. Stearns, Allan Borodin and Paul Young was held at the third annual meeting of the Structure in Complexity conference, and the first three chapters of this book are the final versions of these talks. They recall intellectual and professional trends in Hartmanis' contributions. All but one of the remainder of the chapters in this volume originated as a presentation at one of the recent meetings of the Structure in Complexity Theory Conference and appeared in preliminary form in the conference proceedings. In all, these expositions form an excellent description of much of contemporary complexity theory.

This book surveys theoretical computer science, presenting fundamental concepts and results. Updated and revised, the new edition includes two new chapters on nonuniform complexity, circuit complexity and parallel complexity, and randomized complexity.

This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations.  Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable.  Substantial new content in this edition includes:

a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp─Lipton.a chapter studying properties of the fundamental probabilistic complexity classesa study of the alternating Turing machine and uniform circuit classes. an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Todaa thorough treatment of the proof that IP is identical to PSPACE

With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential andpractical learning tool.

 

Topics and features:

Concise, focused  materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes Contains information that otherwise exists only in research literature and presents it in a unified, simplified mannerProvides key mathematical background information, including sections on logic and number theory and algebra Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes

The theory of computing provides computer science with concepts, models, and formalisms for reasoning about both the resources needed to carry out computa­ tions and the efficiency of the computations that use these resources. lt provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with other problems. Courses in this subject help students gain an­ alytic skills and enable them to recognize the limits of computation. For these reasons, a course in the theory of computing is usually required in the graduate computer science curriculum. The barder question to address is which topics such a course should cover. We believe that students should learn the fundamental models of computation, the limitations of computation, and the distinctions between feasible and intractable. In particular, the phenomena ofNP-completeness and NP-hardness have pervaded much of science and transformed computer science. One option is to survey a large nurober of theoretical subjects, typically focusing on automata and formal languages. However, these subjects are less important to theoretical computer sci­ ence, and to computer science as a whole, now than in the past. Many students have taken such a course as part of their undergraduate education. We chose not to take that route because computability and complexity theory are the subjects that we feel deeply about and that we believe are important for students to learn. Furthermore, a graduate course should be scholarly. lt is better to treat important topics thoroughly than to survey the field.

This book surveys theoretical computer science, presenting fundamental concepts and results. Updated and revised, the new edition includes two new chapters on nonuniform complexity, circuit complexity and parallel complexity, and randomized complexity.

On May 1, 2004, the world of theoretical computer science su?ered a stunning loss: Shimon Even passed away. Few computer scientists have had as long, s- tained, and in?uential a career as Shimon. Shimon Even was born in Tel-Aviv in 1935. He received a B.Sc. in Elect- cal Engineering from the Technion in 1959, an M.A. in Mathematics from the University of Northern Carolina in 1961, and a Ph.D. in Applied Mathematics from Harvard University in 1963. He held positions at the Technion (1964–67 and 1974–2003), Harvard University (1967–69), the Weizmann Institute (1969– 74), and the Tel-Aviv Academic College (2003-04). He visited many universities and research institutes, including Bell Laboratories, Boston University, Cornell, Duke, Lucent Technologies, MIT, Paderborn, Stanford, UC-Berkeley, USC and UT-Dallas. Shimon Even played a major role in establishing computer science education in Israel and led the development of academic programs in two major insti- tions: the Weizmann Institute and the Technion. In 1969 he established at the Weizmann the ?rst computer science education program in Israel, and led this program for ?ve years. In 1974 he joined the newly formed computer science department at the Technion and shaped its academic development for several decades. These two academic programs turned out to have a lasting impact on the evolution of computer science in Israel.