A simple way to reduce factorization problems to SAT

2017/06/23 by Davide Maran, Maran, Davide
Computer Science · #03D15 #68Q15 #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · pdf · doi:10.48550/arxiv.1708.02844

openalex publication_date 2017/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

As Cook-Levin theorem showed, every NP problem can be reduced to SAT in polynomial time. In this paper I show a simpler and more efficent method to reduce some factorization problems to the satisfability of a boolean formula.

Related

• On the complexity of SAT
• The number system hidden inside the Boolean satisfiability problem
• A Critique of Kumar's "Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and Its Implications on P versus NP problem."
• A Critique of a Polynomial-time SAT Solver Devised by Sergey Gubin
• Polynomial Time Algorithm for Boolean Satisfiability Problem