Polynomial Exact-3-SAT-Solving Algorithm

  • Authors

    • Matthias Mueller independent
    2020-08-04
    https://doi.org/10.14419/ijet.v9i3.30749
  • 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. [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.

  • Downloads

  • How to Cite

    Mueller, M. (2020). Polynomial Exact-3-SAT-Solving Algorithm. International Journal of Engineering & Technology, 9(3), 670-691. https://doi.org/10.14419/ijet.v9i3.30749

    Received date: 2020-05-16

    Accepted date: 2020-07-17

    Published date: 2020-08-04