13
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ AFAIK, we don't have a notion of Turing machines corresponding to monotone circuits. So the answer is no. $\endgroup$
    – Kaveh
    Commented Jun 17, 2015 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
    Commented Jun 17, 2015 at 20:00

2 Answers 2

Reset to default
15
$\begingroup$

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}$.

Improve this answer
$\endgroup$
7
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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