Complexity in Computer Science
-
Select format
-
- Publisher:
- Cambridge University Press
- Publication date:
- 09 October 2026
- 19 November 2026
- ISBN:
- 9781009752329
- 9781009752336
- Dimensions:
- (254 x 178 mm)
- Weight & Pages:
- 1.718kg, 750 Pages
- Dimensions:
- Weight & Pages:
You may already have access via personal or institutional login
Show more authors 
You may already have access via personal or institutional login
Book description
Computational complexity theory is about the fundamental capabilities and limitations of efficient computation. Framing the subject in the broader context of computer science, this guidebook is both a self-contained tutorial for beginning graduate students in all areas of computer science and a thorough reference for specialists. Using only elementary discrete math, the book rigorously covers the central concepts of time, space, and randomness in computing, as well as connections to other areas of computer science such as cryptography and machine learning. Intuitions and general techniques are emphasized. The book features full proofs, numerous concrete examples and illustrations, and hundreds of exercises.
Reviews
‘Watson’s Complexity in Computer Science is a comprehensive introduction to computational complexity. It is especially well suited for students new to the area who want to learn both the foundations of the field and its connections to other areas of computer science, such as cryptography and learning theory. Its breadth and level of detail make it an invaluable resource for students.’
Shachar Lovett - University of California, San Diego
Contents
Metrics
Full text views
Full text views helpTotal number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...
* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.
Usage data cannot currently be displayed.
Accessibility standard: WCAG 2.2 A
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.
Accessibility Information
The PDF of this book complies with version 2.2 of the Web Content Accessibility Guidelines (WCAG), offering more comprehensive accessibility measures for a broad range of users and meets the basic (A) level of WCAG compliance, addressing essential accessibility barriers.
Content Navigation
Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Reading Order and Textual Equivalents
Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.