A Proposed SAT Algorithm

α
muham08
muham08
σ
Dr. Bagais A.
Dr. Bagais A.
ρ
Junaidu S. B.
Junaidu S. B.
Ѡ
Abdullahi M.
Abdullahi M.
α Ahmadu Bello University Ahmadu Bello University

Send Message

To: Author

A Proposed SAT Algorithm

Article Fingerprint

ReserarchID

1IAVT

A Proposed SAT Algorithm Banner

AI TAKEAWAY

Connecting with the Eternal Ground
  • English
  • Afrikaans
  • Albanian
  • Amharic
  • Arabic
  • Armenian
  • Azerbaijani
  • Basque
  • Belarusian
  • Bengali
  • Bosnian
  • Bulgarian
  • Catalan
  • Cebuano
  • Chichewa
  • Chinese (Simplified)
  • Chinese (Traditional)
  • Corsican
  • Croatian
  • Czech
  • Danish
  • Dutch
  • Esperanto
  • Estonian
  • Filipino
  • Finnish
  • French
  • Frisian
  • Galician
  • Georgian
  • German
  • Greek
  • Gujarati
  • Haitian Creole
  • Hausa
  • Hawaiian
  • Hebrew
  • Hindi
  • Hmong
  • Hungarian
  • Icelandic
  • Igbo
  • Indonesian
  • Irish
  • Italian
  • Japanese
  • Javanese
  • Kannada
  • Kazakh
  • Khmer
  • Korean
  • Kurdish (Kurmanji)
  • Kyrgyz
  • Lao
  • Latin
  • Latvian
  • Lithuanian
  • Luxembourgish
  • Macedonian
  • Malagasy
  • Malay
  • Malayalam
  • Maltese
  • Maori
  • Marathi
  • Mongolian
  • Myanmar (Burmese)
  • Nepali
  • Norwegian
  • Pashto
  • Persian
  • Polish
  • Portuguese
  • Punjabi
  • Romanian
  • Russian
  • Samoan
  • Scots Gaelic
  • Serbian
  • Sesotho
  • Shona
  • Sindhi
  • Sinhala
  • Slovak
  • Slovenian
  • Somali
  • Spanish
  • Sundanese
  • Swahili
  • Swedish
  • Tajik
  • Tamil
  • Telugu
  • Thai
  • Turkish
  • Ukrainian
  • Urdu
  • Uzbek
  • Vietnamese
  • Welsh
  • Xhosa
  • Yiddish
  • Yoruba
  • Zulu

Abstract

This paper reviews existing SAT algorithms and proposes a new algorithm that solves the SAT problem. The proposed algorithm differs from existing algorithms in several aspects. First, the proposed algorithm does not do any backtracking during the searching process that usually consumes significant time as it is the case with other algorithms. Secondly, the searching process in the proposed algorithm is simple, easy to implement, and each step is determined instantly unlike other algorithms where decisions are made based on some heuristics or random decisions. For clauses with three literals, the upper bound for the proposed algorithm is O(1.8171 n ). While some researchers reported better upper bounds than this, those upper bounds depend on the nature of the clauses while our upper bound is independent of the nature of the propositional formula.

References

28 Cites in Article
  1. A Barbour (1992). Solutions to the minimization problem of fault-tolerant logic circuits.
  2. R Bruni,A,S (2003). A Complete Adaptive Algorithm for Propositional Satisfiability.
  3. Stephen Cook (1971). The complexity of theorem-proving procedures.
  4. J Crawford,A Baker (1994). Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems.
  5. E Danstin,A Goerdt,E Hirsch,R Kannan,J Kleinberg,C Papadimitriou (2002). A Deterministic (2-2 / k+1)n Algorithm fork-SAT based on Local Search.
  6. Martin Davis,Hilary Putnam (1960). A Computing Procedure for Quantification Theory.
  7. M Davis,H Putnam (1960). A Computing Procedure for Quantification Theory.
  8. Martin Davis,George Logemann,Donald Loveland (1962). A machine program for theorem-proving.
  9. S Devadas (1989). Optimal layout via Boolean satisfiability.
  10. J Freeman (1995). Improvements to Propositional Satisfiability Search Algorithms.
  11. E Hirsch (2000). New Worst Case Upper Bounds for SAT.
  12. E Hirsch (1998). Two New Upper Bounds for SAT.
  13. Mark Doms,Chris Forman (1994). Prices for Local Area Network Equipment.
  14. R Jeroslow,J Wang (1990). Solving Propositional Satisfiability Problems.
  15. H Kauts,B Selman (1992). Planning as Satisfiability.
  16. O Kullmann (1999). New methods for 3-SAT decision and worst-case analysis.
  17. T Larrabee (1992). Test pattern generation using Boolean satisfiability.
  18. C Li,Anbulagan (1997). Heuristics Based on Unit Propagation for Satisfiability Problems.
  19. I Lynce,J Marques-Silva (2002). Hidden structure in unsatisfiable random 3-SAT: an empirical study.
  20. Inês Lynce,João Marques-Silva (2002). The Effect of Nogood Recording in DPLL-CBJ SAT Algorithms.
  21. J Marques-Silva,K Sakallah (1999). IEEE Transactions on Computers. GRASP-A Search Algorithm for Propositional Satisfiability.
  22. B Monien,E Speckenmeyer (1985). Solving satisfiability in less than 2n steps.
  23. M Moskewicz,C Madigan,Y Zhao,L Zhang,S Malik (2001). Chaff: engineering an efficient SAT solver.
  24. D Pretolani (1993). Efficiency and stability of hypergraph SAT algorithms.
  25. K Rosen (1999). Handbook of Discrete and Combinatorial Mathematics.
  26. Ingo Schiermeyer (1993). Solving 3-satisfiability in less than 1, 579n steps.
  27. U Schoning (1999). A probabilistic algorithm for k-SAT and constraint satisfaction problems.
  28. Richard Stallman,Gerald Sussman (1977). Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis.

Funding

No external funding was declared for this work.

Conflict of Interest

The authors declare no conflict of interest.

Ethical Approval

No ethics committee approval was required for this article type.

Data Availability

Not applicable for this article.

How to Cite This Article

muham08. 1969. \u201cA Proposed SAT Algorithm\u201d. Global Journal of Computer Science and Technology - D: Neural & AI GJCST-D Volume 13 (GJCST Volume 13 Issue D1): .

Download Citation

Journal Specifications

Crossref Journal DOI 10.17406/gjcst

Print ISSN 0975-4350

e-ISSN 0975-4172

Version of record

v1.2

Issue date

Language
en
Experiance in AR

Explore published articles in an immersive Augmented Reality environment. Our platform converts research papers into interactive 3D books, allowing readers to view and interact with content using AR and VR compatible devices.

Read in 3D

Your published article is automatically converted into a realistic 3D book. Flip through pages and read research papers in a more engaging and interactive format.

Article Matrices
Total Views: 25796
Total Downloads: 11125
2026 Trends
Related Research

Published Article

This paper reviews existing SAT algorithms and proposes a new algorithm that solves the SAT problem. The proposed algorithm differs from existing algorithms in several aspects. First, the proposed algorithm does not do any backtracking during the searching process that usually consumes significant time as it is the case with other algorithms. Secondly, the searching process in the proposed algorithm is simple, easy to implement, and each step is determined instantly unlike other algorithms where decisions are made based on some heuristics or random decisions. For clauses with three literals, the upper bound for the proposed algorithm is O(1.8171 n ). While some researchers reported better upper bounds than this, those upper bounds depend on the nature of the clauses while our upper bound is independent of the nature of the propositional formula.

Our website is actively being updated, and changes may occur frequently. Please clear your browser cache if needed. For feedback or error reporting, please email [email protected]

Request Access

Please fill out the form below to request access to this research paper. Your request will be reviewed by the editorial or author team.
X

Quote and Order Details

Contact Person

Invoice Address

Notes or Comments

This is the heading

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

High-quality academic research articles on global topics and journals.

A Proposed SAT Algorithm

Dr. Bagais A.
Dr. Bagais A.
Junaidu S. B.
Junaidu S. B.
Abdullahi M.
Abdullahi M.

Research Journals