Hvis man skal sammenligne hvor vanskelige to problemer A og B er, hvorfor vil man redusere fra A til B? Problemstillingen dukker opp i ulike forkledninger i flere eksamensoppgaver,1 og viser seg å være vanskelig for mange å få helt grepet på.

Logikken er ganske rett frem:

A kan reduseres til B   betyr   A kan løses ved å løse B.

  • B kan ikke være enklere enn A.
    Hvorfor? Er det enkelt å løse B, har vi en enkel løsning på A.

  • A kan være enklere enn B.
    Hvorfor? Det kan finnes andre måter å løse A på.

Akkurat hva «enkelt» og «enklere» betyr kommer an på hva slags reduksjon vi bruker.

Se også:


  1. For eksempel des. 2008, oppg. 1f, des. 2010, oppg. 3, des. 2011, oppg. 1h, aug. 2012, oppg. h, des. 2014, oppg. 2e, des. 2015, oppg. 18, nov. 2019, oppg. 17, nov. 2020, oppg. 8, aug. 2021, oppg. 9 og des. 2022, oppg. 14 ↩