komplexitet

mått på beräkningars hanterlighet, det vill säga hur lång tid det tar att slutföra dem. – Detta ställs i relation till problemets längd, som för enkelhetens skull mäts i antalet tecken. Triviala exempel är additionen 3+3, multiplikationen 3*3 och 3^3 (tre upphöjt till tre). De består av lika många tecken, men de är olika svåra att genomföra och har alltså olika komplexitet. Naturligtvis är det mer relevant att analysera mer avancerade problem. Man skiljer mellan tre klasser av problem: klassen P, klassen NP och de NP-fullständiga problemen.