<p>There is actually a notion of <em>deterministic</em> positive Turing machine which matches mP/Poly. It can be found in the article <a href="http://www.sciencedirect.com/science/article/pii/S0890540198927420">Positive Versions of Polynomial Time</a> by Lauteman, Schwentick and Stewart</p>

CC BY-SA 3.0
2015-06-19T22:30:14.473Z
2015-06-21T16:42:01.893Z
2015-06-21T16:42:01.893Z
Thomas S
<p>There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper <a href="http://dl.acm.org/citation.cfm?id=167706">Monotone Complexity</a> 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}$.</p>

CC BY-SA 3.0
2015-06-18T12:37:48.960Z
2015-06-18T12:37:48.960Z
Jan Johannsen
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2015-06-17T19:19:12.607Z
AFAIK, we don't have a notion of Turing machines corresponding to monotone circuits. So the answer is no.
Kaveh
CC BY-SA 3.0
2015-06-17T20:00:41.887Z
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
<cc.complexity-theory><complexity-classes><circuit-complexity><polynomial-time><monotone>
What is an equivalent definition of mP/poly in terms of a Turing machine?
Jesse Stern
# What is an equivalent definition of mP/poly in terms of a Turing machine?

(Asked by: username_0 on 2015-06-17)

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?

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, polynomial-time, monotone

> **Comments:**
> **username_1**: AFAIK, we don't have a notion of Turing machines corresponding to monotone circuits. So the answer is no.  
> **username_0**: 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?  

---

## 2 answers

### Answer by username_3 on 2015-06-18. Score: 15 | Accepted answer

There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper [Monotone Complexity](http://dl.acm.org/citation.cfm?id=167706) 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}$.


---

### Answer by username_2 on 2015-06-19. Score: 7

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](http://www.sciencedirect.com/science/article/pii/S0890540198927420) by Lauteman, Schwentick and Stewart


---

