Books in Analysis of algorithms and problem complexity

21-30 of 37 results in All results

Computational Complexity: A Quantitative Perspective

• 1st Edition
• Volume 196
• July 7, 2004
• Marius Zimand
• English
• eBook 978-0-08-047666-7

  9 7 8 - 0 - 0 8 - 0 4 7 6 6 6 - 7

There has been a common perception that computational complexity is a theory of "bad news" because its most typical results assert that various real-world and innocent-looking tasks are infeasible. In fact, "bad news" is a relative term, and, indeed, in some situations (e.g., in cryptography), we want an adversary to not be able to perform a certain task. However, a "bad news" result does not automatically become useful in such a scenario. For this to happen, its hardness features have to be quantitatively evaluated and shown to manifest extensively.The book undertakes a quantitative analysis of some of the major results in complexity that regard either classes of problems or individual concrete problems. The size of some important classes are studied using resource-bounded topological and measure-theoretical tools. In the case of individual problems, the book studies relevant quantitative attributes such as approximation properties or the number of hard inputs at each length.One chapter is dedicated to abstract complexity theory, an older field which, however, deserves attention because it lays out the foundations of complexity. The other chapters, on the other hand, focus on recent and important developments in complexity. The book presents in a fairly detailed manner concepts that have been at the centre of the main research lines in complexity in the last decade or so, such as: average-complexity, quantum computation, hardness amplification, resource-bounded measure, the relation between one-way functions and pseudo-random generators, the relation between hard predicates and pseudo-random generators, extractors, derandomization of bounded-error probabilistic algorithms, probabilistically checkable proofs, non-approximability of optimization problems, and others.The book should appeal to graduate computer science students, and to researchers who have an interest in computer science theory and need a good understanding of computational complexity, e.g., researchers in algorithms, AI, logic, and other disciplines.

Art and Complexity

• 1st Edition
• February 19, 2003
• J. Casti + 1 more
• English
• Hardback 978-0-444-50944-4

  9 7 8 - 0 - 4 4 4 - 5 0 9 4 4 - 4
• eBook 978-0-08-052758-1

  9 7 8 - 0 - 0 8 - 0 5 2 7 5 8 - 1

This title is the result of a one-week workshop sponsored by the Swedish research agency, FRN, on the interface between complexity and art. Among others, it includes discussions on whether "good" art is "complex" art, how artists see the term "complex", and what poets try to convey in word about complex behavior in nature.

Mathematical Logic

• 1st Edition
• Volume 4
• December 5, 2001
• R.O. Gandy + 1 more
• English
• eBook 978-0-08-053592-0

  9 7 8 - 0 - 0 8 - 0 5 3 5 9 2 - 0

Mathematical Logic is a collection of the works of one of the leading figures in 20th-century science. This collection of A.M. Turing's works is intended to include all his mature scientific writing, including a substantial quantity of unpublished material. His work in pure mathematics and mathematical logic extended considerably further; the work of his last years, on morphogenesis in plants, is also of the greatest originality and of permanent importance. This book is divided into three parts. The first part focuses on computability and ordinal logics and covers Turing's work between 1937 and 1938. The second part covers type theory; it provides a general introduction to Turing's work on type theory and covers his published and unpublished works between 1941 and 1948. Finally, the third part focuses on enigmas, mysteries, and loose ends. This concluding section of the book discusses Turing's Treatise on the Enigma, with excerpts from the Enigma Paper. It also delves into Turing's papers on programming and on minimum cost sequential analysis, featuring an excerpt from the unpublished manuscript. This book will be of interest to mathematicians, logicians, and computer scientists.

Handbook of Computability Theory

• 1st Edition
• Volume 140
• October 1, 1999
• E.R. Griffor
• English
• eBook 978-0-08-053304-9

  9 7 8 - 0 - 0 8 - 0 5 3 3 0 4 - 9

The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers.

Compression Algorithms for Real Programmers

• 1st Edition
• September 30, 1999
• Peter Wayner
• English
• eBook 978-0-08-050243-4

  9 7 8 - 0 - 0 8 - 0 5 0 2 4 3 - 4

In life, time is money, and on the Internet, the size of data is money. Small programs and small files take less disk space and cost less to send over the Internet. Compression Algorithms for Real Programmers describes the basic algorithms and approaches for compressing information so you can create the smallest files possible. These new algorithms are making it possible for people to take impossibly large audio and video files and compress them enough that they can flow over the Internet.

Recursive Model Theory

• 1st Edition
• Volume 1
• November 30, 1998
• Y.L. Ershov + 3 more
• English
• eBook 978-0-08-053369-8

  9 7 8 - 0 - 0 8 - 0 5 3 3 6 9 - 8

Recursive Algebra, Analysis and Combinatorics

• 1st Edition
• Volume 2
• November 30, 1998
• Y.L. Ershov + 3 more
• English
• eBook 978-0-08-053370-4

  9 7 8 - 0 - 0 8 - 0 5 3 3 7 0 - 4

Handbook of Proof Theory

• 1st Edition
• Volume 137
• July 9, 1998
• S.R. Buss
• English
• Hardback 978-0-444-89840-1

  9 7 8 - 0 - 4 4 4 - 8 9 8 4 0 - 1
• eBook 978-0-08-053318-6

  9 7 8 - 0 - 0 8 - 0 5 3 3 1 8 - 6

This volume contains articles covering a broad spectrum of proof theory, with an emphasis on its mathematical aspects. The articles should not only be interesting to specialists of proof theory, but should also be accessible to a diverse audience, including logicians, mathematicians, computer scientists and philosophers. Many of the central topics of proof theory have been included in a self-contained expository of articles, covered in great detail and depth.The chapters are arranged so that the two introductory articles come first; these are then followed by articles from core classical areas of proof theory; the handbook concludes with articles that deal with topics closely related to computer science.

Computability, Complexity, and Languages

• 2nd Edition
• February 3, 1994
• Martin Davis + 2 more
• English
• Hardback 978-0-12-206382-4

  9 7 8 - 0 - 1 2 - 2 0 6 3 8 2 - 4
• eBook 978-0-08-050246-5

  9 7 8 - 0 - 0 8 - 0 5 0 2 4 6 - 5

Computability, Complexity, and Languages is an introductory text that covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability.

Constraints, Language and Computation

• 1st Edition
• January 14, 1994
• M. A. Rosner + 2 more
• English
• eBook 978-0-08-050296-0

  9 7 8 - 0 - 0 8 - 0 5 0 2 9 6 - 0

Constraint-based linguistics is intersected by three fields: logic, linguistics, and computer sciences. The central theme that ties these different disciplines together is the notion of a linguistic formalism or metalanguage. This metalanguage has good mathematical properties, is designed to express descriptions of language, and has a semantics that can be implemented on a computer. Constraints, Language and Computation discusses the theory and practice of constraint-based computational linguistics. The book captures both the maturity of the field and some of its more interesting future prospects during a particulary important moment of development in this field.