Authors: Matthias Mueller
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. |
Comments: 55 Pages.
Download: PDF
[v1] 2012-12-17 07:58:51
[v2] 2013-12-13 07:21:02
[v3] 2015-05-10 11:38:40
[v4] 2015-11-11 11:19:40
[v5] 2016-02-24 18:28:19
[v6] 2016-05-10 11:37:43
[v7] 2016-06-15 08:46:27
[v8] 2017-01-22 18:01:27
[v9] 2017-01-23 12:05:27
[vA] 2017-11-05 11:10:50
[vB] 2018-04-14 16:53:02
[vC] 2018-11-17 14:19:06
[vD] 2020-05-10 13:58:32
Unique-IP document downloads: 6625 times
Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.
Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.