reducibilidad de Weihrauch

Noción de Computabilidad

En análisis computable , la reducibilidad de Weihrauch es una noción de reducibilidad entre funciones multivaluadas en espacios representados que captura aproximadamente la fuerza computacional uniforme de los problemas computacionales . ^[1] Fue introducido originalmente por Klaus Weihrauch en un informe técnico inédito de 1992. ^[2]

Definición

Un espacio representado es un par de un conjunto y una función parcial sobreyectiva . ^[1] ${\textstyle (X,\delta )}$ ${\displaystyle X}$ ${\displaystyle \delta :\subset \mathbb {N} ^{\mathbb {N} }\rightarrow X}$

Sean espacios representados y sea una función parcial multivaluada. Un realizador de for es una función (posiblemente parcial) tal que, para cada , . Intuitivamente, un realizador se comporta "como " pero funciona con nombres. Si es un realizador de lo que escribimos . ${\displaystyle (X,\delta _{X}),(Y,\delta _{Y})}$ ${\displaystyle f:\subset X\rightrightarrows Y}$ ${\displaystyle f}$ ${\displaystyle F:\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }}$ ${\displaystyle p\in \mathrm {dom} f\circ \delta _{X}}$ ${\displaystyle \delta _{Y}\circ F(p)=f\circ \delta _{X}(p)}$ ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle F\vdash f}$

Sean espacios representados y funciones parciales multivaluadas. Decimos que Weihrauch es reducible a y escribimos si existen funciones parciales computables tales que ${\displaystyle X,Y,Z,W}$ ${\displaystyle f:\subset X\rightrightarrows Y,g:\subset Z\rightrightarrows W}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\leq _{\mathrm {W} }g}$ ${\displaystyle \Phi ,\Psi :\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }}$

$${\displaystyle (\forall G\vdash g)(\Psi \langle \mathrm {id} ,G\Phi \rangle \vdash f),}$$

espacio de Baire^{[ cita necesaria ]}hacia adelantehacia atrás ${\displaystyle \Psi \langle \mathrm {id} ,G\Phi \rangle :=\langle p,q\rangle \mapsto \Psi (\langle p,G\Phi (q)\rangle )}$ ${\displaystyle \langle \cdot \rangle }$ ${\displaystyle \Psi }$ ${\displaystyle f\leq _{\mathrm {W} }g}$ ${\displaystyle \Phi ,\Psi }$ ${\displaystyle p\mapsto \Psi (p,q)}$ ${\displaystyle f}$ ${\displaystyle q}$ ${\displaystyle g(\Phi (p))}$ ${\displaystyle \Phi ,\Psi }$

Decimos que Weihrauch es fuertemente reducible a y escribimos si el funcional hacia atrás no tiene acceso a la entrada original. En símbolos: ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\leq _{\mathrm {sW} }g}$ ${\displaystyle \Psi }$

$${\displaystyle (\forall G\vdash g)(\Psi G\Phi \vdash f).}$$

Ver también

• Reducibilidad del wadge

Referencias

1. Brattka, Vasco; Gherardi, Guido; Pauly, Arno (2021), Brattka, Vasco; Hertling, Peter (eds.), "Weihrauch Complexity in Computable Analysis", Manual de computabilidad y complejidad en el análisis , Cham: Springer International Publishing, págs. 367–417, arXiv : 1707.03202 , doi : 10.1007/978-3-030- 59234-9_11, ISBN 978-3-030-59233-2, S2CID  7903709 , consultado el 29 de junio de 2022
2. Los grados de discontinuidad de algunos traductores entre representaciones de números reales (Reporte). Instituto Internacional de Ciencias de la Computación. 1992.