Relazione tra la dimensione del circuito e la dimensione della formula nel testo di Sipser

Question

The testo sipser (3rd edizione) contiene una prova che 3-SAT è completo a base di circuiti booleani. Parte della prova contiene l'osservazione che la riduzione del circuito alla formula booleana può essere eseguita in tempo polinomiale.

Prima domanda: è corretto dire che se esiste un circuito c di dimensioni polinomiali, allora deve esistere una formula $ \ varphi $ di dimensioni polinomiali dove c è soddisfacente se e solo se $ \ Varphi $ è soddisfacente?

Seconda domanda: è la formula booleana $ \ varphi $ ancora di dimensione polinomiale se c è di dimensioni polinomiali e c deriva da un deterministico Turing Machine m? Ciò sembra essere descritto nella prova del teorema precedente a Sipser dove (edificio c da un tableau di m) è dimostrato che se $ \ mbox {A $ \ in $ tempo $ (t (n)) $ per $ t (n) \ geq n $ e $ n \ in \ mathbbs {n} $} $ Quindi A ha complessità del circuito $ O (t ^ 2 (n)) $ .

Answer 1

Sì, è corretto.Vedi il Tseitin Transforre , che descrive come.Non importa come il circuito $ c $ è stato costruito.