Complexitat computacional

La teoria de complexitat computacional és la part de la teoria de la computabilitat que estudia els recursos requerits durant el càlcul per resoldre un problema. Els recursos comunament estudiats són el temps (nombre de passos d'execució d'un algorisme per resoldre un problema) i l'espai (quantitat de memòria utilitzada per soldre un problema). Poden estudiar-se igualment altres paràmetres, com el nombre de processadors necessaris per resoldre el problema en paral·lel. La teoria de la complexitat difereix de la teoria de la computabilitat en què aquesta última s'ocupa de la factibilitat d'expressar problemes com algorismes efectius sense tenir en compte els recursos necessaris per aconseguir-ho.

Els problemes que tenen una solució amb ordre de complexitat lineal són els problemes que es resolen en un temps que es relaciona linealment amb la seva mida.

Avui en dia les màquines resolen problemes mitjançant algorismes que tenen com a màxim una complexitat o cost computacional polinòmic, és a dir, la relació entre la mida del problema i el seu temps d'execució és polinòmic. Aquests són els problemes agrupats en el conjunt P. Els problemes amb cost factorial o combinatori estan agrupats en el conjunt NP. Aquests problemes no tenen una solució pràctica, és a dir, una màquina no pots resoldre'ls en un temps raonable.