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.

matematikk | informatikk

NP-úplnost | NP-Vollständigkeit | NP-complete | NP-completo | NP-완전 | NP-Completo | מחלקת סיבוכיות NPC | NP-compleet | NP完全問題 | Problem NP-zupełny | NP-completo | NP-полная задача | NP-úplný problém | เอ็นพีบริบูรณ์