Forstå NP-kompleksitet: definisjon og eksempler

NP står for "Nondeterministisk polynomtid". Det er en kompleksitetsklasse som refererer til hvor lang tid det tar å løse et problem. I NP kan kjøretiden til en algoritme v
re polynom i størrelsen på inngangen, men den kan også v
re ikke-deterministisk, noe som betyr at kjøretiden kan variere avhengig av den spesifikke løsningen valgt av algoritmen.

Med andre ord er NP en klasse av problemer som kan løses i polynomisk tid på en ikke-deterministisk maskin. En ikke-deterministisk maskin er en maskin som kan prøve alle mulige løsninger på et problem parallelt, og akseptere den første som fungerer. Dette gjør at maskinen kan løse noen problemer mye raskere enn en deterministisk maskin, som bare kan prøve én løsning om gangen.

Noen eksempler på problemer i NP inkluderer:

* Problemet med reisende selger (gitt en liste over byer og deres parvise avstander, finn den korteste mulige ruten som besøker hver by nøyaktig én gang)
* Ryggsekkproblemet (gitt et sett med gjenstander og deres vekter og verdier, bestem undersettet av gjenstander som skal inkluderes i en ryggsekk med begrenset kapasitet som maksimerer den totale verdien)
* Det boolske tilfredshetsproblemet (gitt et sett med boolske variabler og deres begrensninger, avgjør om det finnes en tilordning av verdier til variablene som tilfredsstiller alle begrensningene)

NP-kompleksitetsklassen er viktig fordi den inkluderer mange problemer som er vanskelige å løse i polynom. tid, men kan verifiseres raskt av en deterministisk maskin. Dette betyr at selv om en algoritme kanskje ikke kan finne en løsning i polynomisk tid, kan den likevel v
re nyttig hvis den kan verifisere en foreslått løsning raskt.