ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Revisiting Cook-Levin theorem using NP-Completeness and Circuit-SAT

Journal: International Journal of Advanced Engineering Research and Science (Vol.7, No. 3)

Publication Date:

Authors : ;

Page : 206-213

Keywords : Cook-Levin; Boolean satisfiability; circuit-SAT; NP-complete; polynomial time.;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

Stephen Cook and Leonard Levin independently proved that there are problems called NonPolynomial-complete (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 NP-complete through the reduction of polynomial time algorithms for NP-completeness and circuit-SAT.

Last modified: 2020-03-19 13:51:09