Data Structures and Algorithms

1212 Submissions

[2] viXra:1212.0109 [pdf] replaced on 2020-05-10 13:58:32

Polynomial 3-SAT-Solver

Authors: Matthias Mueller
Comments: 55 Pages.

Five different polynomial 3-SAT algorithms named "Algorithm A/B/C/D[M]/E" are provided:
v1: "Algorithm A":  Obsolete, incorrect. My first attempt. In retrospect, this Algorithm A is just a bounded-width logical resolution and thus no polynomial 3-SAT solver.
v2: "Algorithm B":  Obsolete. Never failed for millions of test runs, but I'm not sure if this Algorithm B is really correct. Some time after publishing, I found out that the algorithm keeps too many tuples enabled, for some SAT CNFs. Mr. M. Prunescu's paper 'About a surprizing computer program of Matthias Mueller' is about this Algorithm B.
v3: "Algorithm C":  Obsolete, incorrect. A trial to replace the tuples of Algorithm B by single clauses. Fails for some SAT CNF types (e.g. for large pigeon hole problem CNFs).
v4: "Algorithm D‑1.0":  Obsolete. Never failed, solved absolutely everything that I ever inputted, detected even the pigeon hole problem PHP6 as UNSAT, what would not have been possible if this Algorithm D was just a resolution solver. The problem is that I did not understand the Algorithm D completely (I found it through trial and error, noticed it did never fail). The proof of correctness might not be completely satisfying.
v5: "Algorithm D‑1.1":  Obsolete. Very same algorithm as v4, but better explained and with a re-written, completely new part of the proof of correctness.
v6: "Algorithm D‑1.1":  Obsolete. Some helpful improvements (compared to v5).
v7: "Algorithm D‑1.2":  Obsolete. Paper from May 22nd, 2016.
v8: "Algorithm D‑1.3":  Obsolete. Parts of the proof of correctness have been replaced by a completely re-written, more detailed variant.
v9: "Algorithm D‑1.3":  Obsolete. Another part of the proof of correctness has been made more detailed.
vA: "Algorithm DM‑1.0":  Obsolete. Completely re-written document. Still describes algorithm D, but as short as possible and in mathematical notation.
vB: "Algorithm DM‑2.0":  Obsolete. Heavily revised and extended vA document. A much more precise notation is used (compared to vA) and most formulas are now comprehensively commented and explained. Might be easier to understand for learned readers, while others prefer v9 (D-1.3).
vC: "Algorithm DM‑2.1":  Obsolete. Compared to DM-2.0, three substantial extensions have been added: Why the algorithm does NOT have the restrictions of a logical resolution, that the polynomial solver correctly solved the pigeon hole problem for n=6 ("PHP6"), and what the ideas behind the three rules of the polynomial algorithm are.
vD: "Algorithm E‑1.0":  Please read this paper! This is the newest polynomial solving algorithm, called Algorithm E. Its source code is extremely simple, the main part consists of merely 4 nested loops and does not use tuples of 3-SAT clauses any more to save its internal state but merely single 3-SAT clauses. The first time it is explained in detail how the polynomial algorithm comes about, this time the polynomial algorithm is most widely understood. The algorithm has been extensively tested, the related code and binaries can be downloaded (see below). The algorithm and related paper should be much easier understandable than any of my previous works.
You can also visit www.louis-coder.com/Polynomial_3-SAT_Solver/Polynomial_3-SAT_Solver.htm for latest updates and news, and the Zip file containing the Windows/Linux demo implementation.
Category: Data Structures and Algorithms

[1] viXra:1212.0077 [pdf] submitted on 2012-12-11 09:05:35

A New Algorithm for Linear Programming

Authors: Dhananjay P. Mehendale
Comments: 6 Pages. Presented and Published in the Proceedings of International Conference on Perspectives of Computer Confluence with Sciences 2012, ICPCCS 12.

In this paper we propose a new algorithm for linear programming. This new algorithm is based on treating the objective function as a parameter. We transform the matrix of coefficients representing this system of equations in the reduced row echelon form containing only one variable, namely, the objective function itself, as a parameter whose optimal value is to be determined. We analyze this matrix and develop a clear method to find the optimal value for the objective function treated as a parameter. We see that the entire optimization process evolves through the proper analysis of the said matrix in the reduced row echelon form. It will be seen that the optimal value can be obtained 1) by solving certain subsystem of this system of equations through a proper justification for this act, or 2) By making appropriate and legal row transformations on this matrix in the reduced row echelon form so that all the entries in the submatrix of this matrix, obtained by collecting rows in which the coefficient of so called unknown parameter d whose optimal value is to be determined, become nonnegative and this new matrix must be equivalent to original matrix in the sense that the solution set of the matrix equation with original matrix and matrix equation with transformed matrix are same. We then proceed to show that this idea naturally extends to deal with nonlinear and integer programming problems. For nonlinear and integer programming problems we use the technique of Grobner bases since Grobner basis is an equivalent of reduced row echelon form for a system of nonlinear equations, and the methods of solving linear Diophantine equations respectively.
Category: Data Structures and Algorithms