Wat is complexiteitstheorie — en waarom is ze zo centraal voor de informatica? Complexiteitstheorie bestudeert hoeveel tijd, geheugen of andere middelen nodig zijn om algoritmische problemen op te lossen. Zij vormt het fundament om te begrijpen wat computers kunnen — en wat zelfs met de beste algoritmen in principe onbereikbaar blijft. Van de klassieke klassen P en NP, via reducties, NP-volledigheid en approximatieproblemen, tot interactieve bewijssystemen, de PCP-theorie en communicatiecomplexiteit, leidt dit boek stapsgewijs in de belangrijkste concepten van de theoretische informatica in. Lucien Sina verklaart niet alleen de formele theorie, maar geeft ook de onderliggende ideeën en intuïties. Talrijke voorbeelden, bewijsvoeringen en opgaven met oplossingen helpen de stof te verdiepen en zelf gevoel te krijgen voor de grenzen van efficiënt berekenbare problemen. Het boek is bij uitstek geschikt voor informaticastudenten, docenten, onderzoekers en iedereen die op zoek is naar een gedegen en tegelijk helder toegankelijke inleiding in de complexiteitstheorie. Het sluit aan bij andere werken van de auteur — *Algoritmen en datastructuren*, *Computatietheorie*, *Logica: grondslagen, het P versus NP-probleem en information-theoretische perspectieven*, en *Objectgeoriënteerd programmeren in Java* — en vormt samen een samenhangende leer- en naslagreeks die loopt van fundamenteel onderzoek tot praktische programmering. Complexiteitstheorie toont hoe diep theorie en praktijk van de informatica met elkaar verstrengeld zijn — en waarom het kennen van de grenzen van het haalbare vaak de eerste stap is om ze creatief te verleggen.
