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: 2020-03-10
Authors : Edward E. Ogheneovo;
Page : 206-213
Keywords : Cook-Levin; Boolean satisfiability; circuit-SAT; NP-complete; polynomial time.;
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.
Other Latest Articles
- Preventive Respiratory Physiotherapy with Incentive in spirometer assistance in School Teachers EBI Adventist Education Center
- Operational performance indicators of Brazilian Airport Services, 2013-2016
- Efficient Automatic Food Ordering System using FPGA and ZigBee
- Epidemiological profile of elderly women with Cervical Cancer in the State of Pará/ Brazil in the historical series 2000-2017
- Cancer Mortality in the North Region of Brazil in the Historical Series 2010-2017
Last modified: 2020-03-19 13:51:09