Beziehung zwischen der Schaltungsgröße und der Formelgröße in SIPSER-Text

Question

der Sipsertext (3RD Edition) enthält einen Beweis, dass 3-Sat ist NP-komplett basierend auf booleschen Stromkreisen. Ein Teil des Beweiss enthält die Bemerkung, dass die Reduktion von der Schaltung an die boolesche Formel in der Polynomzeit erfolgen kann.

erste frage: ist es richtig zu sagen, dass, wenn eine circuit c of polynomialgröße vorhanden ist, dann eine formel $ \ varphi $ der Polynomgröße, in der C Ist erfüllt, wenn und nur wenn $ \ varphi $ erfüllt ist?

zweite frage: ist die boolesche formel $ \ varphi $ noch von der Polynomgröße, wenn c von der Polynomgröße ist, und c wird von einem deterministik Turiermaschine M? Dies scheint im Nachweis des früheren Satzes in SIPSER beschrieben zu werden, wo (durch Bauen von C aus einem Tableau von M) gezeigt wird, dass, wenn $ \ mbox {a $ \ in $ Time $ (t (n)) $ für $ t (n) \ geq n $ und $ n \ in \ mathbb {n} $} $ dann A HAT-Kreislaufkomplexität $ O (t ^ 2 (n)) $ .

Answer 1

ja, das ist richtig.Sehen Sie den tseitin transform , der beschrieben wird.Es ist egal, wie die Circuit- $ C $ aufgebaut wurde.