4
$\begingroup$

Consider the problem $\def\GEN{\mathrm{GEN}}\GEN$: given a ternary relation $R \subseteq X^3$ and a subset $S \subseteq X$, is the closure of $S$ with respect to $R$ equal to the whole set $X$? By this we mean the smallest set $S \subseteq C \subseteq X$ such that $u,v \in C$ and $R(u,v,w)$ implies $w \in C$.

It is known that $\GEN$ is $\mathsf{P}$-complete for arbitrary relations, and $\mathsf{NL}$-complete when the relation $R$ expresses an associative composition law $*$ (i.e. $R(u,v,w)$ holds iff $w = u*v$).

We can define a notion of "associative relation" extending the above situation, as follows: say that $R$ is associative if for each $a,b,d,e \in X$, we have

$\exists c. (R(a,b,c) \wedge R(c,d,e)) \Rightarrow \exists c. (R(a,c,e) \wedge R(b,d,c)).$

So I would like to know: what is the complexity of the $\GEN$ problem for such relations? Also, is it possible to define a notion of "$k$-associative relations" that would induce a hierarchy in the space complexity of the $\GEN$ problem?

$\endgroup$
  • $\begingroup$ Your relations are in effect directed 3-edges (hypergraph edges, with 3 nodes, some of which are sources and some of which are targets). In this setting, to define associativity, only edges with 2 sources and 1 target make sense. For k-ary relationships, you could have $k-1$ sources and $1$ target (generalising functions $f:S^{k-1} \to S$), but you could also have $s>\lfloor k/2 \rfloor$ sources and $t=k-s$ targets (generalising functions $f:S^s \to S^t$). I think whether you should consider only $t=1$ or allow $t>1$ depends on whether you have any particular relations/functions in mind. $\endgroup$ – Niel de Beaudrap Mar 20 '14 at 9:20
  • $\begingroup$ In any case, I think the answer is "yes": you can define such a notion. Your notion of "associative ternary relation" suggests thinking of relations (with designated sources/targets) as a nondeterministic transition which transforms tuples. We're interested here in transitions which shorten them. For instance, if $R(a,b,c)$, then we can (maybe non-uniquely) map $ab \to c$. $R$ being associative means that if there is a transition $abc \to ec \to d$, then there is also a transition $abc \to af \to d$. Generalising this to arbitrary transitions which decrease tuple length is then an exercise. $\endgroup$ – Niel de Beaudrap Mar 20 '14 at 11:56
  • $\begingroup$ An example of a 5-ary associative relationship with three sources and two targets: $R \subseteq \def\R{\mathbb R}\def\vec{\mathbf}\R^2 \times \R^2 \times\R^2 \times\R^2 \times\R^2$, where $R(\vec u,\vec v, \vec w, \vec b_1, \vec b_2) \iff [\mathrm{span}\{ \vec b_1, \vec b_2 \} = \mathrm{span}\{\vec u,\vec v,\vec w\}]$. One "applies $R\,$" by replacing triples $(\vec u,\vec v,\vec w)$ of vectors with a pair $(\vec b_1, \vec b_2)$ of vectors which span the same subspace of $\R^2$. Similarly, there's a 7-ary associative relation on $\R^2$ to simplify specifications of affine subspaces of $\R^2$. $\endgroup$ – Niel de Beaudrap Mar 20 '14 at 14:21
  • $\begingroup$ I understand that you interpret $R$ being $k$-ary associative as the existence of two integers $r,s$ that yield a perfect matching in the graph induced by $R$ on $X^r \times X^s$ (up to renumbering of variables). This does not seem to capture what I want, for instance with $r = 2, s = 1$ this only expresses that the third argument is obtained from the first two by some arbitrary operation. Do you see a way to modify the definition to enforce the associativity? $\endgroup$ – NisaiVloot Mar 21 '14 at 18:19
  • $\begingroup$ Er, no; I don't mean anything to do with a matching. See my second comment above. That's a transformation, and despite my earlier comments about directed hypergraphs, you don't have to read it as in any way having to do with a directed edge. $\endgroup$ – Niel de Beaudrap Mar 22 '14 at 9:59

Your Answer

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

Browse other questions tagged or ask your own question.