I løsningsforslaget står det at man skal redusere fra $B$ til $A$. Hvorfor blir det ikke omvendt? Om man vet at $B$ har polynomisk kjøretid og så reduserer fra $A$ til $B$ i polynomisk tid, vet man ikke da at $A$ også har polynomisk kjøretid?

Basert på e-post fra 2019

Dersom premissene her hadde vært rett, så hadde konklusjonen også vært rett, så resonnementet er gyldig; problemet er bare at et av premissene ikke nødvendigvis stemmer! I oppgaven får vi oppgitt at problem $B$ har kjøretid $\Omega(n^2)$ i verste tilfelle. Men det betyr ikke at $B$ kan løses i polynomisk tid!

Det viktige å få med seg her er skillet mellom øvre og nedre grenser. Om vi har grensen $\Omega(n^2)$ i verste tilfelle, så forteller det oss at det ikke kan bli bedre enn det! For alt vi vet, kan det hende at vi også kunne ha satt grensen $\Omega(2^n)$. Så en polynomisk reduksjon fra $A$ til $B$ vil ikke fortelle oss noe om $A$. Det generelle resonnementet her er grundig forklart i en annen FAQ-post

Det som også er viktig å få med seg her, er at det ikke noe sted i oppgaven er snakk om polynomisk kjøretid. Det vi blir bedt om å vise er at grensen $\Omega(n^2)$ også gjelder for $A$. Det betyr at vi må ha en reduksjon fra $B$ til $A$ som er raskere enn dette. Om $T_A$, $T_B$ og $T_R$ er kjøretidene for $A$, $B$ og reduksjonen, så har vi at $T_B\leq T_R + T_A$, altså at $T_A + T_R = \Omega(n^2)$. Dersom f.eks. $T_R = O(n)$, sitter vi igjen med at $T_A = \Omega(n^2)$, som er det vi ville vise.

Men enkelt sagt:

  1. Vil du vise at en øvre grense for $X$ også gjelder for $Y$, må du redusere fra $Y$ til $X$; og
  2. Vil du vise at en nedre grense for $X$ også gjelder for $Y$, må du redusere fra $X$ til $Y$.

I det første tilfellet må kjøretiden til reduksjonen være (asymptotisk) lik den øvre grensen du prøver å vise; i det andre tilfellet må den være (asymptotisk) strengt lavere. (Dette er også diskutert i problemløsningsguiden.) Hvorfor? Som sagt, så er dette forklart ganske grundig i en annen post, men her er en slags analogi …

I stedet for asymptotisk notasjon, la oss bruke $\max$ for å kombinere kjøretider, og la oss oppgi kjøretidene som tall. Grunnen til at vi bruker $\max$ er at vi da får ca. samme oppførsel som asymptotisk notasjon. F.eks.:

\[\Theta(n^2) + \Theta(n^3) = \Theta(n^3)\]

… som tilsvarer $\max(2, 3) = 3$. Vi lar $x$, $y$ og $r$ være kjøretidene for $X$, $Y$ og reduksjonen.

La oss si du vet at $x\leqslant 10$ og vil vise at $y\leqslant 10$. Om du reduserer fra $y$ til $x$, vet du at:

\[y \leqslant \max(r, x); \enskip x\leqslant 10\]

Om $r>10$, så sier det oss ingenting, men om $r\leq 10$, så vet vi at $y\leq 10$.

Hva om du heller vet at $x\geqslant y$ og vil vise at $y \geqslant 10$? Da kan vi redusere den andre veien, og få den omvendte ulikheten:

\[10 \leqslant x \leqslant \max(r, y)\]

Hva skal til for at vi skal kunne konkludere $y\geqslant 10$? Dersom $r \geqslant 10$, så vet vi ingenting, men dersom $r < 10$, så må $y\geqslant 10$.