Computational Intractability

Name: Computational Intractability
Price: 181.64 AUD
Availability: PreOrder
ISBN: 9780262550772

A Guide to Algorithmic Lower Bounds

Erik D. Demaine, William Gasarch Gasarch, MohammadTaghi Hajiaghayi

$213.95 $181.64

Hardback

Forthcoming
Pre-Order now

QTY:

English

MIT Press
22 September 2026

Computing: general

A practical guide to understanding the theory and practice of computational lower bounds.

A fundamental question in computer science is: “Given a problem, how hard is it to solve?” Usually, the answer to this question lies in determining how long it will take to solve a problem as a function of the length of the input. Yet this question has two different parts, with two different answers: (1) upper bounds, which show that a problem can be solved in time T(n), and (2) lower bounds, which show that a problem cannot be solved in time T(n). In Computational Intractability, Erik Demaine, William Gasarch, and Mohammad Hajiaghayi focus on the latter, providing a guidebook to navigating lower bounds via the study of P, NP, NP-completeness, and other related notions.

Computational Intractability covers virtually all aspects of lower bounds, from parallelism to undecidability, and explores this material from the point of view of actual problems rather than classes of problems. The authors show how to prove lower bounds on problems in a wide variety of settings: polynomial time, classes likely above polynomial time (e.g., polynomial space), and classes within polynomial time (e.g., quadratic time).

By: Erik D. Demaine, William Gasarch Gasarch, MohammadTaghi Hajiaghayi
Imprint: MIT Press
Country of Publication: United States
Dimensions: Height: 229mm, Width: 178mm,
Weight: 567g
ISBN: 9780262550772
ISBN 10: 0262550776
Pages: 600
Publication Date: 22 September 2026
Audience: General/trade , ELT Advanced
Format: Hardback
Publisher's Status: Forthcoming

Erik D. Demaine is Professor of Computer Science at MIT and a MacArthur Fellow. His previous books include Geometric Folding Algorithms and Games, Puzzles, and Computation. William Gasarch is Professor of Computer Science at the University of Maryland, where his research focuses on complexity theory, combinatorics, and Ramsey Theory. His previous books include Problems with a Point and Mathematical Muffin Morsels. MohammadTaghi Hajiaghayi is Jack and Rita G. Minker Professor of Computer Science at the University of Maryland. He is a Guggenheim Fellow, ACM Fellow, IEEE Fellow, AAAS Fellow, EATCS Fellow, and Blavatnik Honoree.