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?

Improve this question
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 9:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.