NP-complexiteit begrijpen: definitie en voorbeelden

NP staat voor ‘Niet-deterministische Polynomiale Tijd’. Het is een complexiteitsklasse die verwijst naar de hoeveelheid tijd die nodig is om een probleem op te lossen. In NP kan de looptijd van een algoritme polynoom zijn wat betreft de grootte van de invoer, maar het kan ook niet-deterministisch zijn, wat betekent dat de looptijd kan variëren afhankelijk van de specifieke oplossing die door het algoritme wordt gekozen. Met andere woorden, NP is een klasse van problemen die in polynomiale tijd kunnen worden opgelost op een niet-deterministische machine. Een niet-deterministische machine is een machine die alle mogelijke oplossingen voor een probleem parallel kan uitproberen en de eerste kan accepteren die werkt. Hierdoor kan de machine sommige problemen veel sneller oplossen dan een deterministische machine, die slechts één oplossing tegelijk kan proberen. Enkele voorbeelden van problemen in NP zijn: * Het handelsreizigersprobleem (gegeven een lijst met steden en hun paarsgewijze afstanden, vind de kortst mogelijke route die elke stad precies één keer bezoekt)* Het knapzakprobleem (bepaal, gegeven een reeks voorwerpen en hun gewichten en waarden, de subset van voorwerpen die in een knapzak met een beperkte capaciteit moeten worden opgenomen die de totale waarde maximaliseert)* Het Booleaanse bevredigbaarheidsprobleem (bepaal, gegeven een reeks Booleaanse variabelen en hun beperkingen, of er een toewijzing van waarden aan de variabelen bestaat die aan alle beperkingen voldoet)

De NP-complexiteitsklasse is belangrijk omdat deze veel problemen omvat die moeilijk op te lossen zijn in polynoom tijd, maar kan snel worden geverifieerd door een deterministische machine. Dit betekent dat, hoewel een algoritme misschien niet in polynomiale tijd een oplossing kan vinden, het toch nuttig kan zijn als het een voorgestelde oplossing snel kan verifiëren.