v., onderdeel van de wiskunde, dat zich bezighoudt met het onderzoek van algoritmen en hun implementatie op computers.
© De complexiteitstheorie is van groot belang voor de informatica en de dataverwerking. Computers kunnen nl. principieel alleen problemen oplossen die vast omschreven zijn, waar met andere woorden algoritmen voor bestaan. Het bestaan van een algoritme voor een bepaald probleem hoeft echter nog niet in te houden dat het probleem oplosbaar is. De tijd die een computer nodig heeft voor het oplossen van een probleem hangt immers rechtstreeks af van het aantal stappen (berekeningen of handelingen) dat voor het oplossen ervan nodig is. Als dit aantal stappen b.v. exponentieel afhangt van de grootte van het probleem, dan wordt de oplostijd al snel onmogelijk groot. Zulks problemen, b.v. het→ handelsreizigersprobleem, worden onhanteerbaar genoemd.
Een van de hoofdonderwerpen van de complexiteitstheorie is dan ook de zgn. tijdscomplexiteit. De complexiteitstheorie onderzoekt hoe het aantal stappen van een bepaald algoritme afhangt van de grootte van het probleem en probeert eventueel een sneller algoritme te vinden. Men maakt onderscheid tussen deterministische en niet-deterministische algoritmen. Bij de laatste worden tijdens het rekenproces een of meer keuzen gedaan. Dit maakt dat het gevolgde rekenproces niet van te voren precies voorspelbaar is (wel kan men zeggen: het gaat zo of anders zo). De complexiteitstheorie heeft bewezen dat het altijd mogelijk is een niet-deterministisch algoritme te vervangen door een deterministisch, maar de complexiteit van het deterministisch is gewoonlijk aanzienlijk groter.
Men noemt problemen hanteerbaar, als zij beschreven kunnen worden door algoritmen waarvan het aantal stappen slechts polynomiaal afhangt van de grootte van het probleem. Er is bewezen dat er een klasse van problemen bestaat die wel beschreven kunnen worden door middel van algoritmen, maar niet met een algoritme met een polynomiaal karakter.
Naast het probleem van de tijdscomplexiteit is er het probleem van de ruimtecomplexiteit, d.w.z. de vraag naar de ruimte (d.i. het aantal geheugenplaatsen) die nodig is voor het oplossen van een probleem met een bepaald algoritme.
