Finkornig reduktion

I beräkningskomplexitetsteori är en finkornig reduktion en transformation från ett beräkningsproblem till ett annat, som används för att relatera svårigheten att förbättra tidsgränserna för de två problemen. Intuitivt ger det en metod för att lösa ett problem effektivt genom att använda lösningen på det andra problemet som en subrutin . Om problem $A$ kan lösas i tid $a(n)$ och problem $B$ kan lösas i tid $b(n)$ , då förekomsten av en $(a,b)$ -reduktion från problem $A$ till problem $B$ antyder att varje betydande snabbhet för problem $B$ skulle också leda till en snabbare uppgång för problem $A$ .

Definition

Låt $A$ och $B$ vara beräkningsproblem, specificerade som önskad utdata för varje möjlig ingång. Låt $a$ och $b$ båda vara tidskonstruerbara funktioner som tar ett heltalsargument $n$ och ger ett heltalsresultat. Vanligtvis $a$ och $b$ tidsgränserna för kända eller naiva algoritmer för de två problemen, och ofta är de monomer som $n^{2}$ .

Då sägs ${\displaystyle A} vara$$(a,b)$ -reducerbar till $B$ om, för varje reellt tal $\epsilon >0$ , det finns ett reellt tal $\delta >0$ och en algoritm som löser instanser av problem $A$ genom att omvandla det till en sekvens av instanser av problem $B$ , vilket tar tid $O{\bigl (}a(n)^{1-\delta }{\bigr )}$ för transformationen på instanser av storlek $n$ , och producerar en sekvens av instanser vars storlekar $n_{i}$ begränsas av $\sum _{i}b(n_ {i})^{1-\epsilon }<a(n)^{1-\delta }$ .

En $(a,b)$ -reduktion ges av avbildningen från $\epsilon$ till paret av en algoritm och $\delta$ .

Implikation för snabbare

Antag att $A$ är $(a,b)$ -reducerbar till $B$ , och det finns $\epsilon >0$ så att ${\ displaystyle B}$ kan lösas i tiden $O{\bigl (}b(n)^{1-\epsilon }{\bigr )}$ . Sedan, med dessa antaganden, finns det också $\delta >0$ så att $A$ kan lösas i tiden $O{\bigl ( }a(n)^{1-\delta }{\bigr )}$ . Låt nämligen $\delta$ vara värdet som ges av $(a,b)$ -reduktionen, och lös $A$ genom att tillämpa transformationen av reduktionen och använda den snabba algoritmen för $B$ för varje resulterande delproblem.

På motsvarande sätt, om $A$ inte kan lösas i tid betydligt snabbare än $a(n)$ , så kan $B$ inte lösas i tid signifikant snabbare än ${ \displaystyle b(n)}$ .

Historia

Finkorniga reduktioner definierades, i det speciella fallet att $a$ och $b$ är lika monomialer, av Virginia Vassilevska Williams och Ryan Williams 2010. De visade också förekomsten av $(n^{3},n^{3})$ -reduktioner mellan flera problem inklusive alla pars kortaste vägar , hitta den näst kortaste vägen mellan två givna hörn i en viktad graf, hitta negativ vikt trianglar i viktade grafer, och testa om en given avståndsmatris beskriver ett metriskt utrymme . Enligt deras resultat har antingen alla dessa problem tidsgränser med exponenter mindre än tre, eller så har ingen av dem.

Termen "finkornig reduktion" kommer från senare arbete av Virginia Vassilevska Williams i en inbjuden presentation vid det 10:e internationella symposiet om parametriserad och exakt beräkning.

Även om den ursprungliga definitionen av finkorniga reduktioner involverade deterministiska algoritmer, har motsvarande begrepp för randomiserade algoritmer och icke-deterministiska algoritmer också övervägts.