Mathematics of the impossible: Computational Complexity, Chapter 5, Completeness: Reducing arbitrary computation

In this chapter we show how to reduce arbitrary computation to 3Sat (and hence to the other problems in section º4.3). What powers everything is the following landmark and, in hindsight, simple result which reduces circuit computation to 3Sat. Theorem 5.1. Given a circuit with gates we can compute in a 3CNF formula in variables such […]