Deciding Boolean Satisfiability in Polynomial Time
| Autor: | Ooh Ufuoma |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.5281/zenodo.7386655 |
| Popis: | The goal of this work is to modify the famous DPLL algorithm to solve all SATs in polynomial time. This work discusses a polynomial time algorithm for solving ALL SATs. {"references":["Aaronson S. and Wigderson A., Algebrization: a new barrier in complexity theory, in STOC, 2008, pp. 731–740","Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. Theorem 10.4.","Baker T. P., Gill J, and Solovay R., Relativizations of the P=?NP question, SIAM Journal on Computing 4:4,431-442, 1975","Cook S. A., The complexity of theorem proving procedures, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151-158, 1971.","Davis M., Logemann G. , and Loveland D., Communications of the ACM 5, 394–397 (1962)","Mironov, Ilya; Zhang, Lintao (2006). Biere, Armin; Gomes, Carla P. (eds.). \"Applications of SAT Solvers to Cryptanalysis of Hash Functions\". Theory and Applications of Satisfiability Testing — SAT 2006. Lecture Notes in Computer Science. Springer. Mathematics Handbook for Science and Engineering, Springer, New York, 2006, 5th ed."]} |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|