A novel approach of solving the CNF-SAT problem
This is an incremental analysis comparing known methods for an NP-Complete problem, relevant to researchers in computational complexity and algorithm design.
The paper analyzed two existing algorithms, PL-Resolution and WalkSAT, for solving the CNF-SAT problem, finding that WalkSAT is faster and more practical for less hard problems, though it lacks completeness guarantees.
In this paper, we discussed CNF-SAT problem (NP-Complete problem) and analysis two solutions that can solve the problem, the PL-Resolution algorithm and the WalkSAT algorithm. PL-Resolution is a sound and complete algorithm that can be used to determine satisfiability and unsatisfiability with certainty. WalkSAT can determine satisfiability if it finds a model, but it cannot guarantee to find a model even there exists one. However, WalkSAT is much faster than PL-Resolution, which makes WalkSAT more practical; and we have analysis the performance between these two algorithms, and the performance of WalkSAT is acceptable if the problem is not so hard.