Az eddigiekben több problémát vizsgáltunk: n szám rendezése, konvex burok meghatározása, Voronoi-diagram meghatározása. Néhány problémát idõ szûke miatt nem tudtunk érinteni. Például a konvex burok meghatározásának problémája 3 dimenzióban is természetes módon felvethetõ. A vizsgálatok során valószínûleg kialakult egy vélemény, hogy a fenti problém'ak közül egyik másik nehezebb mint a többi. Az alábbiak lényege, hogy ez az érzés matematikailag is pontossá tehetõ.
Definíció: Legyen P és Q két probléma. Azt mondjuk, hogy P redukálható Q-ra, ha P egyszerûen megoldható egy Q-t megoldó szubrutin segítségével. Jelölésben P<=Q.
Megjegyzés: A fenti definíció nem egy tökéletesen formális definíció. A szubrutin implementációjáról nincs benne szó. Ezt nem is akarjuk részletezni hiszen csak azt tesszük fel, hogy a Q-t megoldó eljárás rendelkezésünkre áll. A teljes algoritmus futá;sa során a Q-t megoldó szubrutin futásának költségét egy elemi lépésnek számoljuk el. Továbbá szerepel benne az ``egyszerûen'' jelzõ. Ez pontossá tehetõ, de a fellépõ technikai nehézségek miatt nem tárgyaljuk. Arra kell gondolnunk, hogy az eljárás jóval egyszerûbb mint a P probléma közvetlen megoldása. Legtöbb esetben a redukciót mutató eljárás olyan rendkívülien egyszerû, hogy ez magától értetõdõ.
Megjegyzés: P<=Q értelme, hogy Q legalább olyan nehéz mint P.
Példa: Rendezés<= Síkbeli konvex burok meghatározása (a csúcsok kerületi sorrendjével)
Indoklás: A rendezési feladat x(1), x(2), ... , x(n) inputjához számoljuk ki az P(1)=(x(1),x(1)^2), P(2)=(x(2),x(2)^2), ... , P(n)=(x(n), x(n)^2) pontokat a síkon. Konvex burkuk az összes pontot tartalmazza (az y=x^2 függvény garafikonja konvex), P(1)P(n) a konvex burok egy oldala. A kerületi sorrendbõl kiolvasható a rendezett sorrend.
Példa: Síkbeli konvex burokmeghatározása <= Voronoi-diagram meghatározása
Indoklás: A konvex burok meghatározásához adott input esetén számoljuk ki a Voronoi-diagramot. A konvex burok csúcsai pontosan azon pontok, amleyek Vornoi-tartománya egy konvex sokszög és egy szögtartomány összege.
Példa: Térbeli félsíkok metszetének meghatározása <= Térbeli konvex burok meghatározásának problémája
Indoklás: Térbeli dualitás.
Példa: Térbeli konvex burok meghatározásának problémája <= Térbeli félsíkok metszetének meghatározása
Indoklás: Térbeli dualitás.
Példa: Voroni-diagram meghatározása <= Térbeli konvex burok meghatározása
Indoklás: Elég a félterek metszetének meghatározására történõ redukciót leírni. A Voronoi-diagram meghatározásának problémájának mindegyik input pontjához hozzárendelünk egy félteret. A fétér definíali síkja a pont z=x^2+y^2 egyenletõ forgás paraboloidjára történõ vetületében a forgás paraboloidhoz húzott érintõ sík. A féltér a ``felsõ féltér''. A redukció helyessége számolással könnyen ellenõrizhetõ.