# What is an equivalent definition of mP/poly in terms of a Turing machine?

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?

• AFAIK, we don't have a notion of Turing machines corresponding to monotone circuits. So the answer is no. – Kaveh Jun 17 '15 at 19:19
• 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? – 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}$.