kompleksitetsteori

kompleksitetsteori, fagområde inden for datalogi, hvor kompleksiteten af problemers løsning ved hjælp af computer undersøges. Et centralt element er studiet af algoritmers effektivitet i form af enten tidsforbrug eller pladsforbrug under problemløsningen. Dette kaldes tidskompleksitet hhv. pladskompleksitet. Et problem klassificeres efter, hvor effektiv en algoritme til dets løsning der kan findes.

En algoritmes forbrug af resurser stiger, jo større problemer man løser. Derfor udtrykkes forbruget som en funktion af størrelsen af det løste problem. Algoritmens kompleksitet karakteriseres nu af, hvor hurtigt denne funktion vokser, enten for det mest resursekrævende problem af en given størrelse eller i gennemsnit over alle problemer af en given størrelse.

Oftest angives kompleksiteten ved hjælp af O-notation. En algoritme kaldes en O (f (n))-algoritme, hvis algoritmens tidsforbrug for næsten alle problemstørrelser, n, er opadtil begrænset af k∙f (n). Her er k en konstant, der ikke afhænger af n.

En effektiv algoritme er karakteriseret ved, at vækstraten for tidsforbruget er begrænset. En algoritme kaldes god eller polynomielt begrænset, hvis dens tidsforbrug i værste tilfælde vokser som et polynomium i problemets størrelse. Algoritmen er så en O (n^q)-algoritme, hvor q er et tal, der afhænger af algoritmen, men ikke af problemstørrelsen. I modsat fald kaldes algoritmen eksponentiel.

Et problem kan nu klassificeres som let hhv. svært, hvis den bedste kendte algoritme for problemet er polynomielt begrænset hhv. eksponentiel. Et af de mest berømte problemer i kompleksitetsteorien er, hvorvidt klassen P af problemer med polynomielle løsningsalgoritmer er lig klassen NP af problemer, der kan løses af en polynomiel algoritme, hvis der tillades ikke-deterministiske algoritmer.

Værste-tilfælde-kompleksiteten udtrykt ved hjælp af O-notation er ikke altid et godt mål for, hvorledes en algoritmes resurseforbrug vokser i praksis. Dette skyldes dels, at værste-tilfælde er sjældent forekommende, dels at vækstraten kan være mindre end den overgrænse, der angives i O-udtrykket. Samtidig kan konstanten på funktionen f være meget stor.

En algoritmes empiriske kompleksitet bestemmes ved måling af algoritmens effektivitet på inddata af varierende størrelse. Begrebet er mindre veldefineret end værste-tilfælde-kompleksiteteten, men nødvendigt, når en algoritmes egenskaber skal vurderes i praksis.