Reduktion (datalogi)
 |
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2025-07) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
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.