NP-fullständighet, egenskap hos ett antal typer av matematiska problem som med nu kända metoder kan lösas bara med ett beräkningsarbete av en omfattning som är en exponentiell funktion av problemets storlek.