Qual é uma definição equivalente de mP / poli em termos de uma máquina de Turing?

13

P / poly é a classe de problemas de decisão solucionáveis ​​por uma família de circuitos booleanos de tamanho polinomial. Como alternativa, ela pode ser definida como uma máquina de Turing de tempo polinomial que recebe uma sequência de conselhos que é polinomial de tamanho em n e que é baseada apenas no tamanho de n.

mP / poly é a classe de problemas de decisão solucionável por uma família de circuitos booleanos monótonos de tamanho polinomial, mas existe uma definição alternativa natural de mP / poly em termos de uma máquina de Turing de tempo polinomial?

cc.complexity-theory complexity-classes circuit-complexity polynomial-time monotone Jesse Stern
fonte
3
AFAIK, não temos a noção de máquinas de Turing correspondentes a circuitos monótonos. Então a resposta é não.
Kaveh
Achei que poderia ser o caso. Alguma discussão notável, on-line ou em jornais, sobre a questão de expressar classes solucionáveis ​​por famílias de circuitos de tamanho limitado monótonas ou com um número limitado de negações, em termos de uma máquina de Turing com limite de tempo? Suas barreiras específicas para definir essas classes ou as pessoas simplesmente não se incomodam?
Jesse Stern

Respostas:

15

mPmP/poeuy

Jan Johannsen
fonte
7

Na verdade, existe uma noção de máquina de Turing positiva determinística que corresponde a mP / Poly. Pode ser encontrado no artigo Versões positivas do tempo polinomial de Lauteman, Schwentick e Stewart

Thomas S
fonte