Reduktion (datalogi)

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

En reduktion är inom datalogi en metod som transformerar om ett problem till ett annat. Med reduktion kan man visa egenskaper hos problem, t ex visa undre gränser på hur ineffektiva lösningar på problemen måste vara. En viktig användning av reduktioner utgörs av bevis av 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.