What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

Question

Let $L$ be a language and $f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\star$ a function on two parameters with the property that for all $x$ and $y$, $f$ returns an element of $L$ if and only if both $x$ and $y$ are elements of $L$:

$$f(x,y)\in L \iff x\in L\wedge y\in L .$$

Question Do such functions have a name in the literature?

Following are some amusing observations. These functions, which I will call "conjunctive reductions", can be constructed for the complete problems of a variety of complexity classes. For example, for $L=SAT$, take the function $f(\psi, \phi)=\psi\wedge\phi$. Analogously, we may consider "disjunctive reductions", so that $g(\psi,\phi)=\psi\vee\phi$ is a disjunctive reduction over $SAT$. These two reductions work fine over quantified boolean formulas too, so they also work for all levels of the polynomial hierarchy and for PSPACE.

It is easy to construct both conjunctive and disjunctive reductions for the L and NL-Complete languages DSTCON and USTCON: Given two graphs, $G, H$ and two pairs of vertices, $(u,v), (x,y)$, construct a new graph by taking the disjoint union $G\cup H$, add two nodes $s,t$ and add edges $(s,u),(v,x),(y,t)$. A disjunctive reduction puts these two graphs in parallel, rather than in series.

A conjunctive reduction exists for Graph Isomorphism, but no disjunctive reduction obviously exists. Conversely, a disjunctive reduction exists for the Nontrivial Graph Automorphism problem, but I could not find a conjunctive reduction. This surprised me, because I thought these problems were on some level the same, and then I had learned something new about graph isomorphism!

As an obvious last step, one may consider "conjugate reductions", functions such that $f(x)\in L \iff x \not\in L$. Finding such a reduction for Graph Isomorphism would show that it is in coNP. I could find neither a conjunctive, nor a disjunctive, nor a conjugate reduction for the decision version of Factoring.

Answer 1

They are typically called AND-functions. (I'm not joking.) Indeed, this concept has been considered before, and that's what people call them. See, for example, the book by Kobler, Schoning, and Toran on Graph Iso, where they talk about AND- and OR-functions for GI. And, by the way, there is an OR-function for GI (ibid.).

The question of an AND-function for graph automorphism is, I believe, still open :) (as stated in the book above).

Based on your last paragraph, the type of reduction you are talking about can also be generalized to what are called "truth-table" or "tt" reductions. These are non-adaptive Turing reductions (the queries are fixed by the input, but cannot depend on the answer to previous queries). For example, the negation kind of reduction in your last paragraph is a 1-tt reduction (1=number of queries).