Logo

Computational Complexity Theory

e-books in Computational Complexity Theory category

Book cover: Mathematics and ComputationMathematics and Computation
by - Princeton University Press ,
The book provides a broad, conceptual overview of computational complexity theory -- the mathematical study of efficient computation. It is useful for undergraduate and graduate students in mathematics, computer science, and related fields.
(3144 views)
Book cover: Around Kolmogorov Complexity: Basic Notions and ResultsAround Kolmogorov Complexity: Basic Notions and Results
by - arXiv.org ,
Algorithmic information theory studies description complexity and randomness. This text covers the basic notions of algorithmic information theory: Kolmogorov complexity, Solomonoff universal a priori probability, effective Hausdorff dimension, etc.
(6212 views)

Book cover: Communication Complexity (for Algorithm Designers)Communication Complexity (for Algorithm Designers)
by - Stanford University ,
The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
(5949 views)
Book cover: Computability and ComplexityComputability and Complexity
- Wikibooks ,
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is CS and Math students with some background in programming and data structures.
(8740 views)
Book cover: P, NP, and NP-Completeness: The Basics of Complexity TheoryP, NP, and NP-Completeness: The Basics of Complexity Theory
by - Cambridge University Press ,
The main focus of the current book is on the P-vs-NP Question and the theory of NP-completeness. Additional topics that are covered include the treatment of the general notion of a reduction between computational problems.
(9164 views)
Book cover: Think Complexity: Complexity Science and Computational ModelingThink Complexity: Complexity Science and Computational Modeling
by - Green Tea Press ,
This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.
(9164 views)
Book cover: Parallel Complexity TheoryParallel Complexity Theory
by - Prentice Hall ,
The rapid growth of parallel complexity theory has led to a proliferation of parallel machine models. This book presents a unified theory of parallel computation based on a network model. It is the first such synthesis in book form.
(9332 views)
Book cover: Measure-Preserving SystemsMeasure-Preserving Systems
by - University of North Carolina ,
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(10639 views)
Book cover: Algorithmic Randomness and ComplexityAlgorithmic Randomness and Complexity
by - Springer ,
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
(9944 views)
Book cover: Specifying SystemsSpecifying Systems
by - Addison-Wesley Professional ,
This book shows how to write unambiguous specifications of complex computer systems. It provides a complete reference manual for the TLA+, the language developed by the author for writing simple and elegant specifications of algorithms and protocols.
(15488 views)
Book cover: Computability and Complexity from a Programming PerspectiveComputability and Complexity from a Programming Perspective
by - The MIT Press ,
The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.
(11576 views)
Book cover: Foundations of CryptographyFoundations of Cryptography
by - Cambridge University Press ,
The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.
(16602 views)
Book cover: Computational Complexity: A Conceptual PerspectiveComputational Complexity: A Conceptual Perspective
by - Cambridge University Press ,
This book offers a comprehensive perspective to modern topics in complexity theory. It can be used as an introduction as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory.
(11652 views)
Book cover: From Complexity to CreativityFrom Complexity to Creativity
by - Plenum Press ,
This text applies the concepts of complexity science to provide an explanation of all aspects of human creativity. The book describes the model that integrates ideas from computer science, mathematics, neurobiology, philosophy, and psychology.
(15345 views)
Book cover: Complexity and ComputationComplexity and Computation
by - Green Tea Press ,
This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.
(15450 views)
Book cover: Lecture Notes on Computational ComplexityLecture Notes on Computational Complexity
by ,
Notes from a graduate courses on Computational Complexity. The first 15 lectures cover fundamentals, the remaining is advanced material: Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, and more.
(14963 views)
Book cover: Introduction to Computational ComplexityIntroduction to Computational Complexity
by ,
Lecture notes for a graduate course on computational complexity taught at the University of Washington. Alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases.
(9493 views)
Book cover: Introduction to Complexity TheoryIntroduction to Complexity Theory
by ,
Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.
(10583 views)
Book cover: Complexity Theory: A Modern ApproachComplexity Theory: A Modern Approach
by - Cambridge University Press ,
The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.
(17386 views)
Book cover: Complexity TheoryComplexity Theory
by ,
This set of notes gives the broad picture of modern complexity theory, defines the basic complexity classes, gives some examples of each complexity class and proves the most standard relations. The author emphasizes the ideas involved in the proofs.
(16209 views)
Book cover: Algorithms and ComplexityAlgorithms and Complexity
by - AK Peters, Ltd. ,
An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.
(20877 views)