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: 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.
(7059 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.
(5859 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.
(10714 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.
(12322 views)