NP-komplett
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 kjent 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.
