¿Por qué un lenguaje de tiempo polinómico tiene un circuito de tamaño polinomio?

Question

Deseo entender por qué P es un subconjunto de PSCPACE, es por eso que un Langauge de tiempo polinómico tiene un circuito de tamaño polinomial. Leí muchas pruebas como este aquí en la página 2-3, pero todas las pruebas usan la misma técnica utilizada en el teorema de Cook-Levin para convertir el cálculo de M en una entrada de N bit X a un circuito de tamaño polinomio.

Lo que no entiendo es que el circuito resultante depende de la entrada x, porque lo que se está convirtiendo en un circuito es el cálculo de M en la entrada específica x. Por definición de psize, el mismo circuito debe funcionar para todas las entradas en una longitud fija y, por lo tanto, no depende de una entrada específica.

Entonces, ¿cómo es exactamente el proceso de crear una familia de circuitos de tamaño poli para una máquina de Turing determinista de poli-tiempo?

Answer 1

Cook-Levin da un circuito para todas las entradas de un tamaño dado. Entonces, aunque el circuito depende de la entrada $ x $, solo depende del tamaño de la entrada. Entonces, dado TM $ m $ con tiempo de ejecución $ T $, y un número $ N $ (el tamaño de la entrada), Cook-Levin le da un circuito $ C_N $ de tamaño aproximadamente $ T^2 $ que resuelve el problema en todas las entradas de tamaño $ n $. El circuito $ C_N $ no depende de cuáles son los bits de la entrada por $ M $, sin embargo, necesitamos saber los números de bits de entrada, ya que ese será el número de bits de entrada para el circuito.

Answer 2

Intuitivamente, un problema de tamaño polinomial necesita al menos un circuito de tamaño polinomio porque cada paso en el algoritmo/circuito requiere una cierta cantidad de tiempo. Si el circuito pudiera verificar un elemento del lenguaje en tiempo menos que polinomio, entonces también podría hacerse un algoritmo para hacerlo.