Computer Science – Data Structures and Algorithms
Scientific paper
2011-06-03
Computer Science
Data Structures and Algorithms
28 pages, 25 figures, 1 picture
Scientific paper
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(n^3) 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 / \Theta(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.
No associations
LandOfFree
Towards P = NP via k-SAT: A k-SAT Algorithm Using Linear Algebra on Finite Fields does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards P = NP via k-SAT: A k-SAT Algorithm Using Linear Algebra on Finite Fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards P = NP via k-SAT: A k-SAT Algorithm Using Linear Algebra on Finite Fields will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-224086