A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if $$(f\times\mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f)\circ(f\times \mathrm{Id}_{X})=(\mathrm{Id}_{X}\times f)\circ (f\times \mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f).$$

The positive braid monoid $B_{n}^{+}$ is the monoid presented with generators $\sigma_{1},\dots,\sigma_{n-1}$ and relations $\sigma_{i}\sigma_{i+1}\sigma_{i}=\sigma_{i+1}\sigma_{i}\sigma_{i+1}$ and $\sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}$ whenever $|i-j|>1$. A positive braid $b\in B_{n}^{+}$ is said to be simple if it cannot be written in the form $b=b_{0}\sigma_{i}^{2}b_{1}$ for some $i\in\{1,\dots,n-1\}$.

If $f$ satisfies the Yang-Baxter equation, then define a monoid action $\pi_{f,n}:X^{n}\times B_{n}\rightarrow X^{n}$ by letting $$\pi_{f,n}((x_{1},\dots,x_{n}),\sigma_{i})=(x_{1},\dots,x_{i-1},f(x_{i},x_{i+1}),x_{i+2},\dots,x_{n}).$$

Does there exist

  1. a function $f:X^{2}\rightarrow X^{2}$ with satisfying the Yang-Baxter equation where $X$ is finite,

  2. some natural number $c$, and

  3. for $m,n$ are natural numbers, functions $i_{n,m}:\{0,1\}^{n}\rightarrow X^{m},j_{m,n}:X^{m}\rightarrow\{0,1\}^{n}$ such that the maps $(n,m,r)\mapsto i_{n,m}(r),(m,n,x)\mapsto j_{m,n}(x)$ are computable in polynomial time such that

if $C$ is a circuit of width $w$ and depth $d$ that computes a function $F_{C}:\{0,1\}^{m}\rightarrow\{0,1\}^{n}$, then there is some $v\leq w\cdot c$ and positive braid $b\in B_{v}$ where $$F_{C}(x_{1},\dots,x_{m})=j_{v,n}(\pi_{f,n}(i_{m,v}(x_{1},\dots,x_{m}),b)))$$ for all inputs $(x_{1},...,x_{m})\in\{0,1\}^{m}$ such that $b=b_{1}\dots b_{s}$ for some simple braids $b_{1},\dots,b_{s}$ and some $s\leq d\cdot c$?


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.