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

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.

• This is a very common structure and is usually known as homomorpism, or structure-preserving operation. To see this, let x ⊕ y ≔ f(x,y) and P(e) ≔ e ∈ L, then your statement is tatanmount to P(x ⊕ y) = (P x ∧ P y. That is, P is conjunctive: it takes ⊕'s to ∧'s. Dec 8, 2016 at 19:58