¿Cuál es una definición equivalente de mP / poly en términos de una máquina de Turing?

13

P / poly es la clase de problemas de decisión que puede resolver una familia de circuitos booleanos de tamaño polinómico. Alternativamente, se puede definir como una máquina de Turing de tiempo polinómico que recibe una cadena de aviso que tiene un tamaño polinómico en n y que se basa únicamente en el tamaño de n.

mP / poly es la clase de problemas de decisión que puede resolver una familia de circuitos booleanos monótonos de tamaño polinómico, pero ¿existe una definición alternativa natural de mP / poly en términos de una máquina de Turing de tiempo polinomial?

cc.complexity-theory complexity-classes circuit-complexity polynomial-time monotone Jesse Stern
fuente
3
AFAIK, no tenemos una noción de máquinas de Turing correspondientes a circuitos monótonos. Por tanto, la respuesta es no.
Kaveh
Supuse que ese podría ser el caso. ¿Alguna discusión notable, ya sea en línea o en documentos, sobre el tema de expresar clases solucionables por familias de circuito de tamaño limitado que son monótonas o tienen un número limitado de negaciones, en términos de una máquina de Turing limitada por el tiempo? ¿Son sus barreras específicas para definir tales clases, o simplemente la gente no se ha molestado?
Jesse Stern

Respuestas:

15

Existe una noción de una máquina de Turing monótona no determinista y, más generalmente, alterna en el papel Monotone Complexity de Grigni y Sipser. Dado que el tiempo polinomial es lo mismo que el espacio logarítmico alterno, una caracterización de máquina de es la máquina Turing de espacio de registro alterno monótono. Proporcionar una máquina de este tipo con consejos polinómicos dará una definición de máquina de .metroPAGmetroPAG/ /pagoly

Jan Johannsen
fuente