To understand the Karp–Lipton proof in more detail, we consider the problem of testing whether a circuit c is a correct circuit for solving SAT instances of a given size, and show that this circuit testing problem belongs to \Pi_1. That is, there exists a polynomial time computable predicate V such that c is a correct circuit if and only if, for all polynomially-bounded z, V(c,z) is true.
