To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity,

An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$ if, for any choice of $m$ tuples $(t_{11}, ... , t_{1k}), ... , (t_{m1}, ... , t_{mk})$ from $R$, it holds that the tuple obtained from these $m$ tuples by applying $f$ coordinate-wise, $( f (t_{11}, ... , t_{m1}), ... , f (t_{1k}, ... , t_{mk}))$, is in $R$.

Two examples follow, but neither answers this question. Let's say that there's a relation $R$ and function $f$ such that $m > k$. Is $f$ a polymorphism of $R$?

Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

  • $\begingroup$ @DavidRicherby Thanks! (Still sounds like an oddly overarching term to be used in a narrow field, but well. People have been known to invent weird terminology.) Remember that the tag will go away after a while if it's not used again, so if you can ask one or two questions or add the tag to as many existing ones, that would be good in that regard. $\endgroup$ – Raphael Sep 3 '16 at 9:52
  • 1
    $\begingroup$ @Raphael I guess the name is because they're a generalization of homomorphisms, in the sense that a homomorphism maps a tuple in $R$ to a new tuple in $R$, whereas a polymorphism maps a bunch of tuples in $R$ to a new tuple in $R$. I'll have a look for more questions to tag $\endgroup$ – David Richerby Sep 3 '16 at 11:05
  • $\begingroup$ @Raphael Well, it turns out that there are two or three answers that mention polymorphisms and one question that kind of tangentially does. Buuuuuuut, I'd forgotten that "polymorphism" is much more commonly used as a property of type systems. It would probably be too confusing to have "polymorphisms" and "polymorphism" referring to completely different things, and I think it would be more sensible to have a tag for the type system thing. $\endgroup$ – David Richerby Sep 5 '16 at 20:13
  • $\begingroup$ @DavidRicherby I can't comment on that. If you think problems may arise, please open a discussion on Computer Science Meta so some more domain experts can weigh in. Thanks! $\endgroup$ – Raphael Sep 5 '16 at 20:24

Let's say that there's a [$k$-ary] relation $R$ and [$m$-ary] function $f$ such that $m>k$. Is $f$ a polymorphism of $R$?

Maybe, maybe not: it depends on the function and the relation. A given $k$-ary relation may have polymorphisms of arity arity less than, equal to, and/or greater than $k$. In fact, every relation has polymorphisms of all arities. For example, the ($1$-ary) identity function is a polymorphism of every relation, as are the projection functions $f_\ell(x_1, \dots, x_m) = x_\ell$ for all $1\leq \ell\leq m$. (Exercise: check these examples.) Notice that the identity function is just the case $\ell=m=1$.

Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

Check the definition! $f$ is a polymorphism of $R_\land = \{(1,1)\}$ if, and only if, for all $(x_1,x_2),(y_1,y_2),(z_1,z_2)\in R_\land$, we have $(f(x_1,y_1,z_1),f(x_2,y_2,z_2))\in R_\land$. Well, the only tuple in $R_\land$ is $(1,1)$, so we only care about the case $x_1=y_1=z_1=x_2=y_2=z_2=1$. And we see that $f(1,1,1)=1$, so $(f(1,1,1),f(1,1,1))\in R_\land$, so $f$ is, indeed, a polymorphism of $R_\land$. Further, by exactly the same argument, any function such that $f(1, \dots, 1) = 1$ is a polymorphism of $R_\land$.

The polymorphism property is often represented as a table: given a $k$-ary relation $R$ and an $m$-ary function $f$, we can write

$$\begin{matrix} (t_{1,1} & t_{1,2} & \cdots & t_{1,k}) & \in R\\ (t_{2,1} & t_{2,2} & \cdots & t_{2,k}) & \in R\\ \vdots & \vdots & \ddots & \vdots & \\ (t_{m,1} & t_{m,2} & \cdots & t_{m,k}) & \in R\\ \hline (f(t_{1,1}, \dots, t_{m,1}) & f(t_{1,2}, \dots, t_{m,2}) &\cdots & f(t_{1,k}, \dots, t_{m,k})) &\in R \end{matrix}$$

The meaning is that we require that, whenever the tuples above the line are in $R$, the tuple below the line must also be in $R$. Notice that nothing in the structure of the table requires any relation between $k$ and $m$: the property could hold (or not hold) for a relation of any arity and a function of any arity. It's just required that, whenever we write a collection of tuples in $R$ and "apply $f$ to each column", the resulting tuple is always still in $R$.

  • $\begingroup$ Thank you! You say the "polymorphism property is often represented as a table" - I haven't seen this representation, and it is really helpful for understanding what's happening. Could you tell me of a reference or author that uses this, so that I can credit appropriately if I use it to explain the concept to readers? (I could also cite this post, of course, but broader refs that provide more context may be better) $\endgroup$ – Rhyme Sep 3 '16 at 9:18
  • $\begingroup$ @Rhyme I'll have a look and get back to you. I could point you to one of my own papers, but I'm pretty sure we didn't invent it (I know I didn't, and I don't think my co-author did). $\endgroup$ – David Richerby Sep 3 '16 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.