2011/06/03 by Matt Groff, Groff, Matt
Computer Science · #Advanced Graph Theory Research #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #Software Reliability and Analysis Research #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1106.0683
28 pages, 25 figures, 1 picture
openalex publication_date 2011/06/03 · arxiv created 2011/10/01 · arxiv updated 2015/03/19 · openalex created_date 2022/08/29 · openalex updated_date 2026/07/28
The problem of P vs. NP is very serious, and solutions to the problem can help save lives. This article is an attempt at solving the problem using a computer algorithm. It is presented in a fashion that will hopefully allow for easy understanding for many people and scientists from many diverse fields. In technical terms, a novel method for solving k-SAT is explained. This method is primarily based on linear algebra and finite fields. Evidence is given that this method may require rougly O(n3) time and space for deterministic models. More specifically the algorithm runs in time O(P V(n+V)2) with mistaking satisfiable Boolean expressions as unsatisfiable with an approximate probablity 1 / Θ(V(n+V)2)P, where n is the number of clauses and V is the number of variables. It's concluded that significant evidence exists that P=NP. There is a forum devoted to this paper at http://482527.ForumRomanum.com. All are invited to correspond here and help with the analysis of the algorithm. Source code for the associated algorithm can be found at https://sourceforge.net/p/la3sat.