An open letter to scientists and the reference implementation of the Romanov algorithm for the NP-complete 3-SP problem

4.5 months have passed since the previous publication of Romanov’s polynomial algorithm for 3-SP .

During this time, Vladimir Fedorovich and I prepared a version of the article in order to send it to fellow scientists and at the same time implemented a reference implementation of this algorithm in Java.

Article and open letter to scientists

')
For the basis of the article we took the existing publication in English, to which I gave a link in a previous post. The current version differs only in small additions, which should, in our opinion, simplify the understanding of the algorithm and the given evidence. Following the advice of kichik, the article was published on arXiv.org:

Non-Orthodox Combinatorial Models Based on Discordant Structures
arxiv.org/abs/1011.3944

Today we have compiled an open letter, which was sent to some scientists whose contacts could be found (thanks to alexeyrom for the links). The letter is also published on the website, which we made specifically for discussion:

3-SAT: Novel Model
romvf.wordpress.com/2011/01/19/open-letter

If someone has contacts of scientists who are engaged in this subject, please, send them this letter. We will welcome any feedback and comments.

Java reference implementation

In the course of working on a new version of the article, we dealt with the algorithm in order to write a reference implementation in Java. We made it! We published the first version of the application on November 19 on github under the LGPL version 3 license:

Reference Implementation of Romanov's Polynomial Algorithm for Boolean 3-SAT Problem
github.com/anjlab/sat3

Now it is a single-threaded implementation, which is a console application that reads formulas from DIMACS CNF format files and outputs the set to execute a set if the formula is executable, or issues a corresponding message if the formula is not executable. The program maintains a detailed log, which should help readers of the article understand the algorithm.

For the seed, here is a basic graph with a performing set for the example from the article (left) and for a formula with the number of variables equal to 100 (right, clickable):

More description of the results of the application can be found here . There is also a readme on github and several pages on the wiki with explanations of how to run the application.

The latest published version is 1.0.3. But in HEAD there are several additional optimizations that speed up the work of the application by 2 times (version 2.0.0-SNAPSHOT).

What's next

Further work can be divided into several areas.

1. Popularization of the article, in order to show it to the largest possible number of interested people.
   
   Here I hope for the help of Habr. We will also work on publishing an article in a scientific journal; we now have several options.
   
   
2. Creating a productive implementation.
   
   The reference implementation was initially conceived as an aid to readers in familiarizing themselves with the operation of the algorithm. It was assumed that it could work on any personal computer where you can run Java. It is not designed to solve industrial problems of large dimension.
   
   On the one hand, this is hampered by the computational complexity of the algorithm (O (n ^ 4 * m)), on the other hand, by resource constraints, in particular, RAM. There are several development paths: optimization of data structures and algorithms, and parallelization of the algorithm (into several threads, processes, etc.).
   
   If you have a desire to help with this - write, we will look for ways to cooperate.
   
   
3. Solving applied problems.
   
   By itself, the task 3-SP is purely theoretical, but many other applied tasks are reduced to it. Although this is a topic of separate research.