Как называется такая функция

Пусть язык и f : Σ ⋆ × Σ ⋆ → Σ ⋆ функция по двум параметрам со свойством, которое для всех x и y , f возвращает элемент из L тогда и только тогда, когда x и y являются элементами из L :$L$$f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$$x$$y$$f$$L$$x$$y$$L$

Вопрос Есть ли такие функции в литературе?

Ниже приведены некоторые забавные замечания. Эти функции, которые я буду называть « конъюнктивными редукциями », могут быть построены для полных задач различных классов сложности. Например, для возьмем функцию f ( ψ , ϕ ) = ψ ∧ ϕ . Аналогично, мы можем рассмотреть « дизъюнктивные редукции », так что g ( ψ , ϕ ) = ψ ∨ ϕ - дизъюнктивная редукция над S A $L=SAT$$f(\psi, \phi)=\psi\wedge\phi$$g(\psi,\phi)=\psi\vee\phi$$SAT$, Эти два сокращения отлично работают и для количественных логических формул, поэтому они также работают для всех уровней полиномиальной иерархии и для PSPACE.

Легко построить как конъюнктивную, так и дизъюнктивную редукции для языков L и NL-Complete DSTCON и USTCON: для двух графов и двух пар вершин ( u , v ) , ( x , y ) создайте новый граф, взяв непересекающееся объединение G ∪ H , добавьте два узла s , t и добавьте ребра ( s , u ) , ( v , x ) , ( y , t $G, H$$(u,v), (x,y)$$G\cup H$$s,t$$(s,u),(v,x),(y,t)$, Разъединительное сокращение ставит эти два графика параллельно, а не последовательно.

Конъюнктивная редукция существует для изоморфизма графов, но дизъюнктивная редукция явно не существует. Наоборот, дизъюнктивная редукция существует для проблемы автоморфизма нетривиального графа, но я не смог найти конъюнктивную редукцию. Это удивило меня, потому что я думал, что эти проблемы на каком-то уровне одинаковы, а затем я узнал что-то новое об изоморфизме графов!

В качестве очевидного последнего шага можно рассмотреть « сопряженные редукции », такие функции, что $f(x)\in L \iff x \not\in L$

Они обычно называются AND-функциями. (Я не шучу.) Действительно, эта концепция рассматривалась ранее, и именно так их называют люди. См., Например, книгу Коблера, Шонинга и Торана о графе Iso, где они рассказывают об AND- и OR-функциях для GI. И, кстати, есть это ИЛИ-функция для GI (см. Там же).

Я полагаю, что вопрос об AND-функции для автоморфизма графа остается открытым :) (как указано в книге выше).

Исходя из вашего последнего абзаца, тип сокращения, о котором вы говорите, также может быть обобщен до так называемых сокращений «таблицы истинности» или «tt». Это неадаптивные сокращения Тьюринга (запросы фиксируются вводом, но не могут зависеть от ответа на предыдущие запросы). Например, отрицательный тип сокращения в вашем последнем абзаце - сокращение на 1 тонну (1 = количество запросов).