¿Por qué P y P / poly no son trivialmente iguales?

10

La definición de P es un lenguaje que puede decidirse mediante un algoritmo de tiempo polinómico. La definición de P / poly puede tomarse como un lenguaje que puede decidirse por un circuito de tamaño polinómico (ver http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Ahora, ¿por qué no se puede simular un circuito de tamaño polinómico en tiempo polinómico?

dcw
fuente
44
P / poly puede calcular lenguajes indecidibles (ejercicio).
Yuval Filmus
Gracias, pero ¿qué hay de malo en mi argumento: que un circuito de tamaño polinómico se puede simular en tiempo polinómico?
DC
3
Está incorrecto. Los circuitos de tamaño polinómico para diferentes longitudes de entrada podrían ser radicalmente diferentes, por lo que no pueden ser descritos por una sola máquina de Turing.
Yuval Filmus
Gracias, pero ¿en qué parte de la definición P dice que estamos restringidos a una sola máquina de Turing? Todas las definiciones que he visto son como en mathworld.wolfram.com/PolynomialTime.html
dcw
3
@dcw Un lenguaje está en P si hay una máquina de Turing tal que ...
David Richerby

Respuestas:

19

El punto sobre los circuitos es que un circuito tiene un número fijo de entradas. Esto significa que, para definir un lenguaje, necesitamos una familia de circuitos C0,C1,C2, modo que el circuito  Ci te diga qué cadenas de longitud  i en el lenguaje, para cada  i . Esto no requiere que haya una relación entre los circuitos CiCi+1 : podrían ser completamente diferentes. En particular, para cualquier conjunto  SN , puede establecer declarar Ci=true siiS yCi=false paraiS . Incluso siS  es indecidible!

En contraste, un lenguaje está en  P si hay una sola máquina de Turing que le dice si cada entrada posible de cada longitud posible está en el idioma. Ahora, no puedes jugar ningún juego divertido sobre entradas de diferentes longitudes.

Usted es correcto que podemos evaluar cualquier circuito fijo en  P . Pero eso no es necesariamente suficiente para decidir un idioma en P/poly . Para hacer eso, primero tendríamos que calcular la longitud de la entrada, luego usarla para determinar qué circuito  Ci debemos evaluar, y luego evaluar el circuito. Como muestra el ejemplo anterior, la parte de "determinar qué circuito" podría ni siquiera ser computable, y mucho menos computable en tiempo polinómico.

David Richerby
fuente
1
Han pasado años desde que estudié todo esto y (casi) olvidé la definición de , pero leer esta respuesta lo trajo de vuelta: recuerdo haber tenido la misma confusión cuando encontré la definición por primera vez y llegué a la misma resolución / comprensión. :-)P/poly
ShreevatsaR