2019/03/24 by Ortho Flint, Asanka Wickramasinghe, Flint, Ortho +5
Computer Science · Engineering · #68R05 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Formal Methods in Verification #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1903.10081
openalex publication_date 2019/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we provide a deterministic polynomial time algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies (link: polynomial3sat.org).