A new algorithm for Solving 3-CNF-SAT problem

April 04, 2017 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Belal Qasemi arXiv ID 1704.01396 Category cs.DS: Data Structures & Algorithms Citations 0 Venue arXiv.org Last Checked 5 months ago
Abstract
NP-Complete problems have an important attribute that if one NP-Complete problem can be solved in polynomial time, all NP-Complete problems will have a polynomial solution. The 3-CNF-SAT problem is a NP-Complete problem and the primary method to solve it checks all values of the truth table. This task is of the Ξ©(2^n) time order. This paper shows that by changing the viewpoint towards the problem, it is possible to know if a 3-CNF-SAT problem is satisfiable in time O(n^10) or not? In this paper, the value of all clauses are considered as false. With this presumption, any of the values inside the truth table can be shown in string form in order to define the set of compatible clauses for each of the strings. So, rather than processing strings, their clauses will be processed implicating that instead of 2^n strings, (O(n^3)) clauses are to be processed; therefore, the time and space complexity of the algorithm would be polynomial.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted