Förstå NP-komplexitet: definition och exempel

NP står för "Nondeterministisk polynomtid". Det är en komplexitetsklass som hänvisar till hur lång tid som krävs för att lösa ett problem. I NP kan körtiden för en algoritm vara polynom i storleken på ingången, men den kan också vara icke-deterministisk, vilket innebär att körtiden kan variera beroende på den specifika lösning som algoritmen väljer.

Med andra ord är NP en klass av problem som kan lösas i polynomtid på en icke-deterministisk maskin. En icke-deterministisk maskin är en maskin som kan prova alla möjliga lösningar på ett problem parallellt, och acceptera den första som fungerar. Detta gör att maskinen kan lösa vissa problem mycket snabbare än en deterministisk maskin, som bara kan prova en lösning åt gången.

Några exempel på problem i NP inkluderar:

* Problemet med resande försäljare (med tanke på en lista över städer och deras parvisa avstånd, hitta den kortaste möjliga vägen som besöker varje stad exakt en gång)
* ryggsäcksproblemet (med tanke på en uppsättning artiklar och deras vikter och värden, bestäm delmängden artiklar som ska inkluderas i en ryggsäck med begränsad kapacitet som maximerar det totala värdet)
* Det booleska tillfredsställbarhetsproblemet (med tanke på en uppsättning booleska variabler och deras begränsningar, bestäm om det finns en tilldelning av värden till variablerna som uppfyller alla begränsningar)

Komplexitetsklassen NP är viktig eftersom den inkluderar många problem som är svåra att lösa i polynom tid, men kan snabbt verifieras av en deterministisk maskin. Detta innebär att även om en algoritm kanske inte kan hitta en lösning i polynomtid, kan den ändå vara användbar om den snabbt kan verifiera en föreslagen lösning.