Computationele complexiteit

Concepten in de informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Complexiteitsklassen

Complexiteitsklassen

Een animatie van de volledige complexiteitsruimte van problemen

Een afbeelding met de probleemruimte P

Complexity Class -->	P (polynomiale tijd)
What it means	Snel en efficiënt oplosbaar
Example	Een lijst sorteren
Analogy	"Documenten alfabetisch ordenen"
Key Point	Dit zijn "makkelijke" problemen in rekentermen

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

Een afbeelding met de probleemruimtes P en NP

Complexity Class -->	NP (niet-deterministische polynomiale tijd)
What it means	Oplossing is te verifiëren, nieuwe vinden is lastig
Example	Controleren of een Sudoku klopt
Analogy	"Een specifiek document vinden met ontbrekende info"
Key Point	Controleren is "makkelijk", nieuwe oplossingen vinden is moeilijk

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

Een afbeelding met de probleemruimtes P, NP en NP-compleet

Complexity Class -->	NP-compleet
What it means	Moeilijkst in NP. Bijzonder: lost alle NP op
Example	Probleem van de handelsreiziger
Analogy	"Ingewikkelde legpuzzel: makkelijk te controleren, lastig op te lossen"
Key Point	Geen bekende efficiënte oplossing. Als die er is, lost die alles in NP op

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

Een afbeelding met de probleemruimtes P, NP, NP-compleet en NP-moeilijk

Complexity Class -->	NP-moeilijk
What it means	Zo moeilijk als NP-compleet of moeilijker
Example	Optimale planning met complexe afhankelijkheden, niet verifieerbaar
Analogy	"Een optimale vergadertijd plannen met veel constraints, niet snel te checken"
Key Point	Praktisch mogelijk onoplosbaar

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

Een diagram met de aloude onderzoeksvraag: is P=NP?

Concepten in de informatica