2002/05/24 by Charles Sauerbier, Sauerbier, Charles
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #F.1.1 #F.2.2 #FOS: Computer and information sciences #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.cs/0205064
openalex publication_date 2002/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Three algorithms are presented that determine the existence of satisfying assignments for 3SAT Boolean satisfiability expressions. One algorithm is presented for determining an instance of a satisfying assignment, where such exists. The algorithms are each deterministic and of polynomial complexity. The algorithms determining existence are complete as each produces a certificate of non-satisfiability, for instances where no satisfying assignment exists, and of satisfiability for such assignment does exist.