The 1st NP-complete problem:3-SAT Any NP problem can be verified in polynomial time,by definition. Turn the verification algorithm into a formula which checks every step of computation Note that in either circuit definition or Turing machine definition,computation is local. 0 The change of configuration is only at several adjacent locations. 18The 1st NP-complete problem: 3-SAT ◼ Any NP problem can be verified in polynomial time, by definition. ◼ Turn the verification algorithm into a formula which checks every step of computation. ◼ Note that in either circuit definition or Turing machine definition, computation is local. ❑ The change of configuration is only at several adjacent locations. 18