komplexitetsteori (jämför franska complexité, se vidare komplex), gren inom de teoretiska delarna av datalogi, i gränslandet till matematik. Den grundläggande frågan inom komplexitetsteorin är: Vilka beräkningsresurser krävs för att lösa ett givet beräkningsproblem?

Det finns ett antal olika mått på hur mycket resurser en beräkning kräver, men de mått som

(50 av 357 ord)
Vill du få tillgång till hela artikeln?

Medverkande

  • Johan Håstad
Källangivelse
Nationalencyklopedin, komplexitetsteori. http://www.ne.se/uppslagsverk/encyklopedi/lång/komplexitetsteori