NP-komplett
Frå Wikipedia – det frie oppslagsverket
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 «vanskeligast» å 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.
 |
Denne matematikkartikkelen er ei spire. Du kan hjelpe Nynorsk Wikipedia å vekse seg stor og sterk gjennom å utvide han.
Sjå òg: Oversyn over matematikkspirer. |
