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?
10
Respuestas:
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 circuitosC0,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 Ci y Ci+1 : podrían ser completamente diferentes. En particular, para cualquier conjunto S⊆N , puede establecer declarar Ci=true sii∈S yCi=false parai∉S . Incluso siS es indecidible!
En contraste, un lenguaje está enP 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 enP . 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.
fuente