NP-komplett

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

NP-komplett er eit omgrep innan matematikken som står for «Non-Polynomial in Time Complete». NP-komplette problem er dei problema i NP som det er «vanskelegast» å finne effektive algoritmar for. Viss ein finn ein algoritme med polynomisk køyretid for eit NP-komplett problem, tyder det at alle problem i NP kan løysast med algoritmar med polynomisk køyretid, det vil seie at P=NP. Det er ikkje kjend om det er mogleg.

Dersom eit NP-komplett problem skal løysast analytisk, må det som regel nyttast ein algoritme der køyretida aukar eksponensielt med lengda til inndataet.

Spire Denne matteartikkelen er ei spire. Du kan hjelpe Nynorsk Wikipedia gjennom å utvide han.