Reducibilidad de Weihrauch

Noción de computabilidad

En el 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 introducida 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 y espacios representados y sea una función multivaluada parcial. Un realizador para es una función (posiblemente parcial) tal que, para cada , . Intuitivamente, un realizador para se comporta "igual que " pero funciona con nombres. Si es un realizador para escribimos . ${\displaystyle (X,\delta _{X})}$ ${\displaystyle (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 sean funciones parciales multivaluadas. Decimos que es Weihrauch reducible a , y escribimos , si hay funciones parciales computables tales que donde y denota la unión en el espacio de Baire . Muy a menudo, en la literatura encontramos escrito como una función binaria, para evitar el uso de la unión. ^{[ cita requerida ]} En otras palabras, si hay dos aplicaciones computables tales que la función es un realizador para siempre que sea una solución para . Las aplicaciones a menudo se denominan funcionales hacia adelante y hacia atrás respectivamente. ${\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),}$$ ${\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 es fuertemente reducible a Weihrauch y escribimos , si la función inversa 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).}$$

Véase también

• Reducibilidad de Wadge

Referencias

1. Brattka, Vasco; Gherardi, Guido; Pauly, Arno (2021), Brattka, Vasco; Hertling, Peter (eds.), "Complejidad de Weihrauch en análisis computable", Manual de computabilidad y complejidad en 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. Weihrauch, Klaus (1992). Los grados de discontinuidad de algunos traductores entre representaciones de los números reales (Reporte). Informatik-Berichte. vol. 129. FernUniversität de Hagen.