Thus the verification can be encoded into a sequence of local consistency checks. The number of clauses is polynomial The verification algorithm is of polynomial time. Polynomial time also implies polynomial space. This shows that SAT is NP-complete. It turns out that any SAT can be further reduced to 3-SAT problem. 19◼ Thus the verification can be encoded into a sequence of local consistency checks. ◼ The number of clauses is polynomial ❑ The verification algorithm is of polynomial time. ❑ Polynomial time also implies polynomial space. ◼ This shows that SAT is NP-complete. ◼ It turns out that any SAT can be further reduced to 3-SAT problem. 19