Polynomial Exact-3-SAT-Solving Algorithm

Authors

  • Matthias Mueller independent

DOI:

https://doi.org/10.14419/ijet.v9i3.30749

Published:

2020-08-04

Keywords:

2-SAT, 3-SAT, Complexity, P-NP-problem, SAT solver, Satisfiability

Abstract

This article describes an algorithm which is supposed by the author to be capable of solving any instance of a 3-SAT CNF in maximal O(n^15), whereby n is the variable index range within the 3-SAT CNF to solve. The presented algorithm imitates the proceeding of an exponential, fail-safe solver. This exponential solver stores internal data in m-SAT clauses, with 3 <= m <= n. The polynomial solver works similarly, but uses 3-SAT clauses only to save the same data. The paper explains how, and proves why this can be achieved. On the supposition the algorithm is correct, the P-NP-Problem would be solved with the result that the complexity classes NP and P are equal.

References

[1] Michael R. Garey, David S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman & Co., (1979).
[2] Christos H. Papadimitriou, Computational complexity, Addison-Wesley, (1994).
[3] Bronstein, Semendjajew, Musiol, Muhlig, Taschenbuch der Mathematik, ¨ Verlag Harri Deutsch, Thun und Frankfurt am Main, (2000),
ISBN 3-8171-2015-X.
[4] Mihai Prunescu, About a Surprizing Computer Program of Matthias Muller, ¨ https://imar.academia.edu/MihaiPrunescu. Accessed 2020-July-21.
[5] Mihai Prunescu, About a Surprising Computer Program of Matthias Muller, Convexity and Discrete Geometry Including Graph Theory, ¨
Springer International Publishing, Mulhouse, France, (2014), ISBN 978-3-319-28186-5 9, http://dx.doi.org/10.1007/978-3-319-28186-5 9.
Accessed 2020-July-21.
[6] Schoning, Tor ¨ an, The Satisfiability Problem, ´ Lehmanns Media Berlin, (2013), ISBN 978-3-86541-527-1.
[7] Anup Rao, More Pigeons, and a Proof Complexity Lower Bound, https://homes.cs.washington.edu/∼anuprao/pubs/CSE599sExtremal/lecture5.pdf.
Accessed 2020-July-21.

View Full Article: