Många-en minskning

I beräkningsbarhetsteori och beräkningskomplexitetsteori är en många-en-reduktion (även kallad kartläggningsreduktion ) en reduktion som omvandlar instanser av ett beslutsproblem till ett annat beslutsproblem med hjälp av en effektiv funktion. Där instansen reducerad till är på språket $L_{2}$ om den initiala instansen var på sitt språk $L_{1}$ och inte är på språket $L_{ 2}$ om den initiala instansen inte var på sitt språk $L_{1}$ . Så om vi kan avgöra om $L_{2}$ instanser finns i språket $L_{2}$ , kan vi avgöra om $L_{1}$ instanser finns i dess språk genom att tillämpa reduktionen och lösa $L_{2}$ . Således kan reduktioner användas för att mäta den relativa beräkningssvårigheten för två problem. Det sägs att $L_{1}$ reduceras till ${\displaystyle L_{2}} om$$L_{2}$ i lekmannaspråk är svårare att lösa än ${\ displaystil L_{1}}$ . Det vill säga, vilken algoritm som helst som löser $L_{2}$ kan också användas som en del av ett (för övrigt relativt enkelt) program som löser $L_{1}$ .

Många-en-reduktioner är ett specialfall och en starkare form av Turing-reduktioner . Med många-en-reduktioner kan oraklet (det vill säga vår lösning för B) endast anropas en gång i slutet, och svaret kan inte ändras. Det betyder att om vi vill visa att problem A kan reduceras till problem B, kan vi använda vår lösning för B endast en gång i vår lösning för A, till skillnad från i Turing-reduktion, där vi kan använda vår lösning för B så många gånger som behövs när man löser A.

Detta innebär att många-en-reduktioner mappar instanser av ett problem till instanser av ett annat, medan Turing-reduktioner beräknar lösningen på ett problem, förutsatt att det andra problemet är lätt att lösa. Reduktionen med många en är effektivare för att dela upp problem i distinkta komplexitetsklasser. De ökade restriktionerna för många-en-reduktioner gör dem dock svårare att hitta.

Många-en-reduktioner användes först av Emil Post i en tidning publicerad 1944. Senare använde Norman Shapiro samma koncept 1956 under namnet stark reducerbarhet .

Definitioner

Formella språk

Antag att $A$ och $B$ är formella språk över alfabeten $\Sigma$ respektive $\Gamma$ . En reduktion med många en från $A$ till $B$ är en total beräkningsbar funktion $f:\Sigma ^{*}\rightarrow \Gamma ^{*}$ som har egenskapen att varje ord $w$ finns i $A$ om och endast om $f(w)$ finns i $B$ .

Om en sådan funktion $f$ finns, säger vi att $A$ är många-en-reducerbar eller m-reducerbar till $B$ och skriver

$A\leq _{\mathrm {m} }B.$

Om det finns en injektiv många-en-reduktionsfunktion säger vi att A är 1-reducerbar eller en-en-reducerbar till $B$ och skriver

$A\leq _{1}B.$

Delmängder av naturliga tal

Givet två uppsättningar $A,B\subseteq \mathbb {N}$ säger vi att $A$ är många-en reducerbar till $B$ och skriver

$A\leq _{\mathrm {m} }B$

om det finns en total beräkningsbar funktion $f$ med $x\in A$ iff $f(x)\in B$ . Om dessutom $f$ är injektiv säger vi att $A$ är 1-reducerbar till $B$ och skriver

$A\leq _{1}B.$

Om dessutom $f$ är surjektiv , säger vi att $A$ är rekursivt isomorf till $B$ och skriver ^s.324

$A\equiv B$

Många-en-ekvivalens och 1-ekvivalens

Om $A\leq _{\mathrm {m} }B\,\mathrm {and} \,B\leq _{\mathrm {m} }A$ vi säg $A$ är många-en-ekvivalent eller m-ekvivalent med $B$ och skriv

$A\equiv _{\mathrm {m} }B.$

Om $A\leq _{1}B\,\mathrm {och} \,B\leq _{1}A$ säger vi att $A$ är 1-motsvarande B $\displaystyle B}$ och skriv

$A\equiv _{1}B.$

Många-en fullständighet (m-fullständighet)

En uppsättning $B$ kallas många-en komplett , eller helt enkelt m-komplett , om $B$ är rekursivt uppräknad och varje rekursivt uppräknad uppsättning $A$ är m-reducerbar till ${\ displaystil B}$ .

Grader

$\equiv _{m}$ är en ekvivalensrelation, dess ekvivalensklasser kallas m-grader och bildar en poset ${\mathcal {D}}_{m}$ med den inducerade ordningen med $\leq _{m}$ . ^s.257

Vissa egenskaper hos m-graderna, av vilka några skiljer sig från analoga egenskaper hos Turinggrader : ^s.555--581

• Det finns en väldefinierad hoppoperator på m-graderna.
• 00 Den enda m-graden med hopp _m ′ är _m .
• Det finns m-grader $\mathbf {a} >_{m}{\boldsymbol {0}}_{m}'$ där det inte finns $\mathbf {b}$ där $\mathbf {b} '=\mathbf {a}$ .
• Varje räkningsbar linjär ordning med minsta element bäddas in i ${\mathcal {D}}_{m}$ .
• Den första ordningens teori för ${\mathcal {D}}_{m}$ är isomorf till teorin för andra ordningens aritmetik.

Det finns en karaktärisering av ${\mathcal {D}}_{m}$ som den unika poset som tillfredsställer flera uttryckliga egenskaper hos dess ideal , en liknande karaktärisering har gäckat Turing-graderna. ^{s. 574--575}

$\equiv _{1}$ är en ekvivalensrelation, och dess ekvivalensklasser (kallade 1-graderna ) bildar en poset under $\leq _{1}$ . Myhills isomorfismsats kan anges som "för alla mängder $A,B$ av naturliga tal, $A\equiv B\iff A\equiv _{1}B$ ", vilket innebär att $\equiv$ och $\equiv _{1}$ har samma ekvivalensklasser. ^{s. 325}

Många-en-reduktioner med resursbegränsningar

$NC_{0}$ en-reduktioner utsätts ofta för resursbegränsningar, till exempel att reduktionsfunktionen är beräkningsbar i polynomtid, logaritmiskt rum, av $AC_{0}$ eller -kretsar, eller polylogaritmiska projektioner där varje efterföljande reduktionsföreställning är svagare än den tidigare; se polynomtidsreduktion och loggutrymmesreduktion för detaljer.

Givet beslutsproblem $A$ och $B$ och en algoritm N som löser instanser av $B$ , kan vi använda en reduktion av många en från $A$ till ${\ displaystyle B}$ för att lösa instanser av $A$ i:

• den tid som behövs för N plus den tid som behövs för reduktionen
• det maximala utrymmet som behövs för N och det utrymme som behövs för reduktionen

Vi säger att en klass C av språk (eller en delmängd av potensmängden av de naturliga talen) är stängd under många-en-reducerbarhet om det inte finns någon reduktion från ett språk i C till ett språk utanför C . Om en klass är stängd under många-en-reducerbarhet, kan många-en-reduktion användas för att visa att ett problem finns i C genom att reducera ett problem i C till det. Många-en-reduktioner är värdefulla eftersom de flesta välstuderade komplexitetsklasser är stängda under någon typ av många-en-reducerbarhet, inklusive P , NP , L , NL , co-NP , PSPACE , EXP och många andra. Det är till exempel känt att de fyra första listade är stängda för den mycket svaga reduktionsuppfattningen av polylogaritmiska tidsprojektioner. Dessa klasser är dock inte stängda under godtyckliga många-en-reduktioner.

Egenskaper

• Relationerna mellan många-en-reducerbarhet och 1-reducerbarhet är transitiva och reflexiva och inducerar således en förordning på de naturliga talens potensuppsättning .
• $A\leq _{\mathrm {m} }B$ om och endast om $\mathbb {N} \setminus A\leq _{\mathrm {m} }\mathbb {N} \setminus B.$
• En uppsättning är många-en reducerbar till stoppproblemet om och bara om den är rekursivt uppräknad . Detta säger att när det gäller många-en-reducerbarhet är stoppproblemet det mest komplicerade av alla rekursivt uppräknade problem. Därmed är stoppproblemet åter fullständigt. Observera att det inte är det enda re kompletta problemet.
• Det specialiserade stoppproblemet för en enskild Turingmaskin T (dvs den uppsättning ingångar som T slutligen stannar för) är många-ett komplett om T är en universell Turingmaskin . Emil Post visade att det finns rekursivt uppräknade uppsättningar som varken är avgörbara eller m-kompletta, och därför finns det icke -universella Turing-maskiner vars individuella stoppproblem ändå är oavgjorda .

Karpreduktioner

En polynom-tid- många-en-reduktion från ett problem A till ett problem B (som båda vanligtvis krävs för att vara beslutsproblem ) är en polynom-tidsalgoritm för att transformera indata till problem A till indata till problem B , så att den transformerade problemet har samma utdata som det ursprungliga problemet. En instans x av problem A kan lösas genom att tillämpa denna transformation för att producera en instans y av problem B , ge y som indata till en algoritm för problem B och returnera dess utdata. Polynom-tid många-en-reduktioner kan också vara kända som polynomtransformationer eller Karp-reduktioner , uppkallade efter Richard Karp . En reduktion av denna typ betecknas med $A\leq _{m}^{P}B$ eller $A\leq _{p}B$ .