Logo

Computability and Complexity

Small book cover: Computability and Complexity

Computability and Complexity

Publisher: Wikibooks

Description:
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is Computer Science and Math students with some background in programming, data structures, and discrete math, such as a sophomore in a Computer Science program.

Home page url

Download or read it online for free here:
Read online
(online html)

Similar books

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.
(10707 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.
(6239 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.
(4228 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.
(8429 views)