3-SAT: Novel Model

Dear Fellow Researchers,

Would you kindly pay attention to the article “Discordant Compact Logic-Arithmetic Structures in Discrete Optimization Problems” by the author V. F. Romanov published on arXiv.org: http://arxiv.org/abs/1309.6078.

The previous paper of the author introduced the model for effective resolvability of 3-SAT problem based on unique special purpose components: structures of compact triplets and systems of hyperstructures. A concealed shortcoming of the filtration procedure for the complicated hyperstructures didn’t allow considering the model as irreproachable for the totality of input formulas.

The novel model uses, however, the merits of the structures of compact triplets (CTS) and, moreover, their outcome: the structures of compact couples (CCS); the system of CCS forms foundation of the new method and algorithm for 3-SAT problem resolving.

The problem is reduced to elementary detection of n-tuples of zeros in the discordant CCS system, prepared for this purpose by means of a special transformation. The formula is synthesized, being on the structure a variation of 2-CNF, associated with the calculation procedure realizing adaptation of the polynomial algorithm of constraints distribution (well-known in the optimization theory) to the efficient resolving of Boolean formula coded by means of discordant compact structures.

As a whole the described algorithmic model of 3-SAT problem representation and solution belongs to the class of polynomial models. No use of heuristic modes and complicated systems of hyperstructures radically distinguish the given model from earlier workings out of the author.

Your opinion and suggestions concerning my work would be of great value for me.

Yours faithfully, the author Vladimir Romanov

Dear Fellow Researchers,

Would you kindly pay attention to the article “Non-Orthodox Combinatorial Models Based on Discordant Structures” by the author V. F. Romanov published on arXiv.org: http://arxiv.org/abs/1011.3944 (download: PDF, initial format LaTeX, 12pt).

The article presents a constructive proof of effective resolvability of 3-SAT problem, accompanied by description of a polynomial algorithm created for the named purpose.

The proof uses a unique graph-combinatorial model based on the Boolean formulas representation in the form of structures of compact triplets. The proof procedure required the induction principle applied to special constructive components which are systems of hyperstructures.

This work was developed for a period of 10 years by private initiative independently of my professor duties in Vladimir State University. For this time work has been published in several Russian scientific journals. Also two independent versions of the algorithm in programming languages have been implemented.

The first version was developed in parallel with theoretical positions and had been finished in 2002. On its basis statistical computer-aided experiment which is mentioned in paper was accomplished.

The second version was implemented by my colleagues in the end of 2010. In the course of work they used only ready article, in passing offering remarks to the text for the purpose of improvement of its understanding. Successful realization of the algorithm testified to sufficiency of the material stated in the article. Source code of the program is accessible in Internet under license LGPL version 3: https://github.com/anjlab/sat3, also https://romvf.wordpress.com

The fact of existence of the polynomial algorithm for 3-SAT problem leads to a conclusion that P=NP.

Your opinion and suggestions concerning my work would be of great value for me.

Yours faithfully, the author Vladimir Romanov

We are happy to announce that Romanov’s article Non-orthodox combinatorial models based on discordant structures is published on arXiv.org.

Also we have prepared reference implementation of algorithm introduced in the paper and published it as open source (LGPLv3) project on github. Currently this implementation is in public beta and may have bugs. Go grab it, test it and submit issues if you find them.

Any feedback is appreciated.