Reduktion
Sign in to savetransformation of one computational problem to another, used to show that the second problem is as difficult as the first
Wikidata facts
Show 3 more facts
- facet of
- problem solving
- Stack Exchange tag
- cstheory.stackexchange.com/tags/reductions
- maintained by WikiProject
- WikiProject Mathematics
Sources (1)
via Wikidata · CC0
Article · Svenska
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 . 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. Denna datavetenskapsrelaterade artikel saknar väsentlig information. Du kan hjälpa till genom att lägga till den.
Abstract from DBpedia / Wikipedia · CC BY-SA