Relação entre o tamanho do circuito e o tamanho da fórmula no texto da sustentação

Question

o texto da sustentação (3rd edition) contém uma prova de que 3-SAT é NP-completo com base em circuitos booleanos. Parte da prova contém a observação de que a redução do circuito para a fórmula booleana pode ser feita em tempo polinomial.

primeira pergunta: é correto dizer que, se um circuito C de tamanho polinomial existir, então deve existir uma fórmula $ \ varphi $ de tamanho polinômio, onde c é satisfatório se e somente se $ \ varphi $ é satisfatório?

segunda pergunta: é a fórmula booleana $ \ varphi $ ainda de tamanho polinômio se c é de tamanho polinômico e c é derivado de um determinístico Máquina de Turing M? Isso parece ser descrito na prova do teorema anterior em Sipser, onde (construindo C de um Tableau de M) é mostrado que, se $ \ mbox {A $ \ NOME $ (T (n)) $ para $ T (n) \ Geq n $ e $ n \ in \ mathbb {n} $} $ então um tem complexidade de circuito $ O (t ^ 2 (n)) $ .

Answer 1

Sim, isso é correto.Veja o tseitin transformar , que descreve como.Não importa como o circuito $ C $ foi construído.