4
$\begingroup$

Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean function. Denote the two possible simple single crossing tangles by $T_0$ and $T_1$ (your choice for which is which). Is there some "generalized $n$-tangle" (i.e., a bunch of properly embedded arcs in $S^3$ with $n$ disjoint 3-balls removed that are numbered from 1 to $n$ and the boundary of each ball having 4 points of the arcs) $T_f$ so that when given an input $x \in \{0,1\}^n$ the link $T_f(x)$ is an unlink if and only if $f(x) = 0$, where here $T_f(x)$ is obtained by plugging $T_{x_i}$ into the ball labeled $i$ for $1 \leq i \leq n$?

Playing around with some small Boolean functions, I was always able to do this, however I didn't see a general argument for the existence of such a $T_f$.

$\endgroup$
2
  • $\begingroup$ I think the "garden hose" model of communication complexity might be related? arxiv.org/abs/1109.2563 $\endgroup$ Commented Dec 27, 2021 at 3:23
  • $\begingroup$ @JalexStark Thanks for the article - I enjoyed reading it, but unfortunately don't see a real connection. $\endgroup$
    – user101010
    Commented Dec 27, 2021 at 16:43

0

You must log in to answer this question.

Browse other questions tagged .