Forståelse af NP-kompleksitet: Definition og eksempler

NP står for "Nondeterministisk polynomisk tid". Det er en kompleksitetsklasse, der refererer til den tid, det tager at løse et problem. I NP kan køretiden for en algoritme v
re polynomisk i størrelsen af inputtet, men den kan også v
re ikke-deterministisk, hvilket betyder at køretiden kan variere afh
ngigt af den specifikke løsning valgt af algoritmen.

Med andre ord er NP en klasse af problemer, der kan løses i polynomisk tid på en ikke-deterministisk maskine. En ikke-deterministisk maskine er en maskine, der kan prøve alle mulige løsninger på et problem parallelt, og acceptere den første, der virker. Dette gør det muligt for maskinen at løse nogle problemer meget hurtigere end en deterministisk maskine, som kun kan prøve én løsning ad gangen.

Nogle eksempler på problemer i NP omfatter:

* Problemet med den rejsende s
lger (givet en liste over byer og deres parvise afstande, find den kortest mulige rute, der besøger hver by nøjagtigt én gang)
* Rygselproblemet (ud fra et s
t af genstande og deres v
gt og v
rdier, bestemme delm
ngden af genstande, der skal inkluderes i en ransel med begr
nset kapacitet, der maksimerer den samlede v
rdi)
* Det boolske tilfredshedsproblem (givet et s
t af booleske variable og deres begr
nsninger, afgør, om der findes en tildeling af v
rdier til variablerne, der opfylder alle begr
nsningerne)

NP-kompleksitetsklassen er vigtig, fordi den inkluderer mange problemer, der er sv
re at løse i polynomium tid, men kan hurtigt verificeres af en deterministisk maskine. Det betyder, at selvom en algoritme måske ikke kan finde en løsning i polynomisk tid, kan den stadig v
re nyttig, hvis den hurtigt kan verificere en foreslået løsning.