Redusibilitet

Definisjon: En sammenligning mellom vanskelighetsgraden til problemer (algoritmisk).

Dersom vi legger til en ubetydelig mengde arbeid (som tar polynomisk tid) til et problem, $A$, blir det resulterende problemet, $B$, enten like vanskelig, eller vanskeligere. Dette er et veldig forvirrende begrep.

---

Bruk Altså hvis vi har et problem, $A$, som kan reduseres til et problem, $B$, kan vi skrive det slik:

$$A{\le }_{P}B$$

Der ${\le }_P$ er redusibilitetsrelasjonen.

Dette betyr at hvis vi har løsningen på problem $B$, så kan vi lage en algoritme som finner løsningen på problem $A$ basert på løsningen av problem $B$ i Polynomisk tid.

$$\text{ce}Bløseligipolynomisktid\to \text{ce}Aløseligipolynomisktid$$

Merk: Vi gjør et skille på Polynomisk tid og Superpolynomisk tid.

---

Eksempler

Redusering av et beslutningsproblem til et optimeringsproblem.

Gitt beslutningsproblemet A, og optimeringsproblemet B. A: I grafen $G$, finnes det en sti mellom node $u$ og $v$ kortere enn $k$? B: Finn korteste sti mellom $u$ og $v$ i graf $G$.

Da blir reduksjonsalgoritmen som følger

SolveA(G, u, v ,k):
	Let x be the shortest path from u to v given from Bellman-Ford
	
	return x<k

Første linje i pseudokoden tar $O(VE)$ tid, altså Polynomisk tid, og er en løsning på A. Vi bruker denne løsningen i siste linje i pseudokoden, som er løsningen på B. Vi kan derfor si at vi har redusert A til B.

$$A{\le }_{P}B$$