Reduktion (datalogi)

Från Wikipedia
Hoppa till: navigering, sök

En reduktion är inom datalogi en metod att bevisa att ett problem är NP-svårt. För att visa detta löses ett redan känt NP-fullständigt problem med hjälp av det problem som ska visas vara NP-svårt.