En reduktion er en hvad slags idé? Skriv et svar i sammenhæng med det foregående spørgsmål. Det kan være 1 - 20 sætninger. Kontekst:
Mange kompleksitetsklasser defineres ved hjælp af begrebet reduktion. En reduktion er en omdannelse af et problem til et andet problem. Det indfanger den uformelle opfattelse af, at et problem er mindst lige så vanskeligt som et andet problem. For eksempel, hvis et problem X kan løses ved hjælp af en algoritme for Y, X er ikke sværere end Y, og vi siger, at X reducerer til Y. Der er mange forskellige typer af reduktioner, baseret på metoden for reduktion, såsom Cook reduktioner, Karp reduktioner og Levin reduktioner, og den bundne på kompleksiteten af reduktioner, såsom polynomial-tid reduktioner eller log-rum reduktioner.