# Non-boolean monotone planar circuit value problem

It is known that monotone planar boolean circuits have a NC circuit value problem (in fact, much more is known).

What about non-boolean monotone planar circuits?

Precisely, take $Q=\{0,...,n-1\}$ and any family of monotone functions $f_i:Q^2\rightarrow Q$ and consider planar circuits where gates are chosen among the $f_i$. What is known for such circuits?

• I don't think anyone studied this problem. I guess that the MPCVP algorithms for the binary case can be modified in a simple way when the size of Q is constant (by making a more elaborate interval structure). However, if Q is allowed to vary with the input size it seems that the problem is P complete, by having alternate levels of Q representing true and false. – Kristoffer Arnsfelt Hansen May 20 '14 at 18:30