4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Kristoffer Arnsfelt Hansen May 20 '14 at 18:30

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.