Relation entre la taille du circuit et la taille de la formule dans le texte SIPSER

Question

the SIPER Texte (3ème édition) contient une preuve que 3-SAT est NP-complet en fonction des circuits booléens. Une partie de la preuve contient la remarque que la réduction du circuit à la formule booléenne peut être effectuée en temps polynomial.

Première question: est-il correct de dire que si un circuit C de taille polynomiale existe, il doit exister une formule $ \ varphi $ de taille polynomiale où c est satisfible si et seulement si $ \ varphi $ est satisfiablement?

deuxième question: est la formule booléenne $ \ varphi $ toujours de taille polynomiale si c est de taille polynomiale et c est dérivé d'un déterministe tucuring machine m? Cela semble être décrit dans la preuve du théorème antérieur dans le sirotant où (en construisant C à partir d'un tableau de M), il est montré que si $ \ mbox {A $ \ en $ $ (t (n)) $ pour $ t (n) \ geq n $ n \ in \ mathbb {n} $} $ a une complexité de circuit $ O (t ^ 2 (n)) $ .

Answer 1

Oui, c'est correct.Voir le TSEITTIN Transform , qui décrit comment.Peu importe la façon dont le circuit $ C $ a été construit.