Восстанавливаемость ладана

В анализе вычислимом сводимость по Вейрауху — это понятие сводимости между многозначными функциями в представленных пространствах, которое примерно отражает равномерную вычислительную мощность вычислительных задач . ^[1] Первоначально он был представлен Клаусом Вейраухом в неопубликованном техническом отчете 1992 года. ^[2]

Определение

Представленное пространство – это пара ${\textstyle (X,\delta )}$ из набора $X$ и сюръективная частичная функция $\delta :\subset \mathbb {N} ^{\mathbb {N} }\rightarrow X$ . ^[1]

Позволять $(X,\delta _{X}),(Y,\delta _{Y})$ быть представлены пространствами и пусть $f:\subset X\rightrightarrows Y$ быть частичной многозначной функцией. Реализатор для $f$ это (возможно, частичная) функция $F:\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }$ такой, что для каждого $p\in \mathrm {dom} f\circ \delta _{X}$ , $\delta _{Y}\circ F(p)=f\circ \delta _{X}(p)$ . Интуитивно, реализующий $F$ для $f$ ведет себя «так же, как $f$ ", но это работает с именами. Если $F$ является реализатором $f$ мы пишем $F\vdash f$ .

Позволять $X,Y,Z,W$ быть представлены пространствами и пусть $f:\subset X\rightrightarrows Y,g:\subset Z\rightrightarrows W$ быть частичными многозначными функциями. Мы говорим, что $f$ можно ли свести ладан к $g$ , и напиши $f\leq _{\mathrm {W} }g$ , если существуют вычислимые частичные функции $\Phi ,\Psi :\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }$ такой, что $(\forall G\vdash g)(\Psi \langle \mathrm {id} ,G\Phi \rangle \vdash f),$ где $\Psi \langle \mathrm {id} ,G\Phi \rangle :=\langle p,q\rangle \mapsto \Psi (\langle p,G\Phi (q)\rangle )$ и $\langle \cdot \rangle$ обозначает соединение в пространстве Бэра . Очень часто в литературе мы встречаем $\Psi$ написана как двоичная функция, чтобы избежать использования соединения. ^{[ нужна ссылка ]} Другими словами, $f\leq _{\mathrm {W} }g$ если есть два вычислимых отображения $\Phi ,\Psi$ такая, что функция $p\mapsto \Psi (p,q)$ является реализатором $f$ в любое время $q$ это решение для $g(\Phi (p))$ . Карты $\Phi ,\Psi$ часто называют прямым и обратным функционалом соответственно.

Мы говорим, что $f$ сильно сводит ладан к $g$ , и напиши $f\leq _{\mathrm {sW} }g$ , если обратный функционал $\Psi$ не имеет доступа к исходному вводу. В символах: $(\forall G\vdash g)(\Psi G\Phi \vdash f).$

См. также

Сводимость Ваджа

Ссылки

^ Jump up to: ^а ^б Браттка, Васко; Герарди, Гвидо; Поли, Арно (2021), Браттка, Васко; Хертлинг, Питер (ред.), «Сложность Вейрауха в вычислимом анализе» , Справочник по вычислимости и сложности в анализе , Cham: Springer International Publishing, стр. 367–417, arXiv : 1707.03202 , doi : 10.1007/978-3-030- 59234-9_11 , ISBN 978-3-030-59233-2 , S2CID 7903709 , получено 29 июня 2022 г.
^ Вайраух, Клаус (1992). Степени разрыва некоторых трансляторов между представлениями действительных чисел (Отчет). Отчеты по информатике. Том 129. FernUniversität в Хагене.

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

Эта математической логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[:0-1] Jump up to: ^а ^б Браттка, Васко; Герарди, Гвидо; Поли, Арно (2021), Браттка, Васко; Хертлинг, Питер (ред.), «Сложность Вейрауха в вычислимом анализе» , Справочник по вычислимости и сложности в анализе , Cham: Springer International Publishing, стр. 367–417, arXiv : 1707.03202 , doi : 10.1007/978-3-030- 59234-9_11 , ISBN 978-3-030-59233-2 , S2CID 7903709 , получено 29 июня 2022 г.

[2] Вайраух, Клаус (1992). Степени разрыва некоторых трансляторов между представлениями действительных чисел (Отчет). Отчеты по информатике. Том 129. FernUniversität в Хагене.

[1]

[2]