Revisiting Cook-Levin theorem using NP-Completeness and Circuit-SAT
Edward E. Ogheneovo · International Journal of Advanced Engineering Research and Science · 2020
Stephen Cook and Leonard Levin independently proved that there are problems called NonPolynomialcomplete (NP-complete) problems.The theorem is today referred to as Cook-Levin theorem.The theorem states that Boolean satisfiability problem is NP-complete.That is to say, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.Therefore, if there exists a deterministic polynomial time algorithm for solving a Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP.Thus Cook-Levin theorem provides a proof that the problem of SAT is NP-complete via reduction technique.In this paper, we revisit Cook-Levin Theorem but using a completely different approach to prove the theorem.The approach used combines the concepts of NP-completeness and circuit-SAT.Using this technique, we showed that Boolean satisfiability problem is NPcomplete through the reduction of polynomial time algorithms for NP-completeness and circuit-SAT.