P/poly is the class of decision problems solvable by a family of polynomial-size Boolean circuits. It can alternatively be defined as a polynomial-time Turing machine that receives an advice string that is size polynomial in n and that is based solely on the size of n.

mP/poly is the class of decision problems solvable by a family of polynomial-size monotone Boolean circuits, but is there a natural alternative definition of mP/poly in terms of a polynomial-time Turing machine?

  • 3
    $\begingroup$ AFAIK, we don't have a notion of Turing machines corresponding to monotone circuits. So the answer is no. $\endgroup$ – Kaveh Jun 17 '15 at 19:19
  • $\begingroup$ I figured that might be the case. Any notable discussions, either online or in papers, on the issue of expressing classes solvable by bounded size circuit families that are monotone or have a bounded number of negations, in terms of a time bounded Turing machine? Are their specific barriers to defining such classes, or have people simply not bothered? $\endgroup$ – Jesse Stern Jun 17 '15 at 20:00

There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as alternating logarithmic space, a machine characterization of uniform $\mathsf{mP}$ is the monotone alternating logspace Turing machine. Providing such a machine with polynomial advice will then give a machine definition of $\mathsf{mP/poly}$.


There is actually a notion of deterministic positive Turing machine which matches mP/Poly. It can be found in the article Positive Versions of Polynomial Time by Lauteman, Schwentick and Stewart


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.