Polynomial time algorithm for 3-SAT. Examples of use

2007/03/21 by S. A. Gubin, Gubin, Sergey
Computer Science · Engineering · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #G.2.1 #G.2.2 #Logic in Computer Science (cs.LO) #Optimization and Packing Problems #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.cs/0703098

openalex publication_date 2007/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The algorithm checks the propositional formulas for patterns of unsatisfiability.

Related

• Determining satisfiability of 3-SAT in polynomial time
• The 3-satisfiability problem
• A Polynomial Time Algorithm for 3-SAT
• A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
• Algorithm that Solves 3-SAT in Polynomial Time