Datorer finns överallt idag – på jobbet, i våra bilar, i våra vardagsrum och i våra fickor – och har ändrat vår tillvaro mer än vi kunnat drömma om. Och ändå är dessa tekniska underverk när det kommer till kritan förvånansvärt enkla och dumma: allt de kan göra är att mekaniskt skyffla runt ettor och nollor. Hur kraftfulla är egentligen sådana automatiska beräkningsmaskiner? Och var går gränsen för vad man kan åstadkomma med rent mekaniska beräkningar?
Komplexitetsteori gör det möjligt att översätta dessa djupa och fascinerade filosofiska frågor till exakta matematiska resonemang. Varje uppgift som i princip kan lösas med hjälp av dator, dvs genom att mekaniskt följa en given lista med enkla matematiska instruktioner, definierar ett beräkningsproblem. Inom komplexitetsteori fokuserar man på att klassificera sådana beräkningsproblem med avseende på hur svåra de är och på att relatera olika klasser av problem till varandra. Målet är att förstå potentialen hos datorberäkningar men också – och framför allt – vilka begränsningar som finns för vad som kan lösas med datorer, eller av automatiserade beräkningsprocesser mer generellt. Att ett problem är svårt betyder intuitivt att det kräver mycket stora resurser för att lösas oavsett med vilken metod man försöker angripa det (dvs oavsett vilken algoritm som används). Formellt fångar man denna intuition genom att definiera precisa matematiska modeller för beräkningsmaskiner och visa satser om hur mycket resurser som dessa maskiner behöver för att lösa problemet mätt i t.ex. körtid, minnesåtgång, parallellitet, kommunikationsbandbredd, et cetera.
Målet med denna kurs att ge en introduktion till komplexitetsteori, presentera en översikt över några av de viktigaste forskningsresultaten, och diskutera några av de öppna frågor som studeras intensivt inom området idag. Avsikten är att täcka in komplexitetsteori ganska brett, men ändå med viss tyngdpunkt på delområden där Teorigruppen på KTH har lämnat viktiga bidrag till forskningen.