Relación entre tamaño de circuito y tamaño de fórmula en texto Sipser

Question

The texto de Sipser (3rd Edition) contiene una prueba que 3-SAT Está completo en función de los circuitos booleanos. Parte de la prueba contiene la observación de que la reducción del circuito a la fórmula booleana se puede hacer en el tiempo polinomial.

Primera pregunta: ¿Es correcto decir que si existe un circuito C de tamaño polinomial, entonces debe existir una fórmula $ \ varphi $ de tamaño polinomio donde c es satisfecho si y solo si $ \ varphi $ es satisfactorio?

Segunda pregunta: es la fórmula booleana $ \ Varphi $ Aún de tamaño polinomio si C es de tamaño polinomial y C se deriva de un determinista Máquina de Turing M? Esto parece describirse en la prueba del teorema anterior en Sipser donde (mediante la construcción de C de un cuadro de M) se muestra que si $ \ mbox {A $ \ en $ Time $ (t (n)) $ por $ t (n) \ geq n $ y $ n \ in \ mathbb {n} $} $ luego una complejidad de circuito $ O (t ^ 2 (n)) $ .

Answer 1

Sí, eso es correcto.Consulte la Transformación de Tseitin , que describe cómo.No importa cómo se construyó el circuito $ C $ .