Polynomial Exact-3-SAT-Solving Algorithm

 
 
 
  • Abstract
  • Keywords
  • References
  • PDF
  • 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.

  • Keywords


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

  • 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

Download

Article ID: 30749
 
DOI: 10.14419/ijet.v9i3.30749




Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.