Beräkningskomplexitet

Grundläggande datavetenskap

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Komplexitetsklasser

Komplexitetsklasser

En animation som visar hela problemkomplexitetsutrymmet

En bild som visar problemutrymmet P

Komplexitetsklass -->	P (polynomisk tid)
Vad det innebär	Löses snabbt och effektivt
Exempel	Sortera en lista
Analogi	"Arkivera dokument i bokstavsordning"
Viktigt	Dessa är "enkla" i beräkningsteoretisk mening

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

En bild som visar problemutrymmet P och NP

Komplexitetsklass -->	NP (icke-deterministisk polynomisk tid)
Vad det innebär	Lösningen går att verifiera, men är svår att hitta
Exempel	Verifiera att ett Sudoku är korrekt löst
Analogi	"Hitta ett dokument med ofullständig information"
Viktigt	Att verifiera en lösning är "enkelt", men att hitta en ny är svårt

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

En bild som visar problemutrymmet P, NP och NP-fullständigt

Komplexitetsklass -->	NP-fullständigt
Vad det innebär	Svårast inom NP. Löser alla NP-problem
Exempel	Handelsresandeproblemet
Analogi	"Lösa ett komplext pussel – lätt att verifiera, svårt att lösa"
Viktigt	Ingen känd effektiv lösning finns, men hittas en så löser den alla NP-problem

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

En bild som visar problemutrymmet P, NP, NP-fullständigt och NP-svårt

Komplexitetsklass -->	NP-svårt
Vad det innebär	Lika svårt som NP-fullständigt eller svårare
Exempel	Optimal schemaläggning med komplexa beroenden, ej verifierbar
Analogi	"Hitta optimal mötestid med många begränsningar, ej snabbt verifierbar"
Viktigt	Kan vara praktiskt omöjligt att lösa

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Ett diagram som ställer den klassiska forskningsfrågan: gäller P=NP?

Grundläggande datavetenskap