The program has demonstrated that can easily solve up 150 variables of complex SAT instances.
It's main algorithm simply uses real probabilities as inputs (being the sums of Pi and -Pi 1).
Starting from p=0.5 for all the variables, it calculates the entropy[1], or also called uncertainty, of the system (problem) to check how feasible is to solve the system with the given input and then to see how close are we solve it
(Entropy = 0).
Entropy 0 only will be achieved once assigned the correct 0s or 1s and any other in between that does not affect the entropy for the given input.
The algorithm works based on changing gradually the input probabilities of every variable to achieve the 0 entropy of the system.
For a given set of input probabilities the entropy of the system is calculated to every variable set at its two extremes, 0 and 1. This conditioned probability gives us an indicator of where the system is heading if we are closer to 1 or to 0 in every variable probability input.
By readjusting the inputs using this information we reduce gradually the entropy of the system.
Evolution of the algorithm
This method reduces the entropy till you get a point that tough useful to reduce a subset of the problem (say a number of clauses) the rest is remains unsolvable.
At this points different approaches can be made and I am exploring them.
I have started with the less formal but very attractive for me since it is how evolution is based (notice that in this version we consider only the selection and mutation procedures).
I save the input that produces the minimum entropy. Once the entropy reduction algorithm increases the entropy or collapses (infinitum), I reload the saved set that produced the minim entropy so far.
At this point the algorithm adds pseudo-random small increases to the this input probabilities to diverge it from its local minimum situation.
Saving all the sets that achieve a minimum system entropy (evolution part), I add random increases to it and execute the entropy reduction algorithm explained above constantly till get new minimums and finally I achieve a complete set that solves the problem, entropy = 0.
Though beautifully explained and a correct way of adding small random inputs (we want be close to what made this set be a minimum, say its 0s 1s selection), this algorithms finds difficulties solving more than 250 variables of a complex instance[2].
For smaller cases it take just seconds, though as more variable solve, more dependent is on the random selection.
We can say that it finds bigger subsets of 1s and 0s that are more close to solve the whole problem till arriving to a subset equal to the whole problem.
I can say it always finds bigger subsets (less entropy for the problem), but the peace at which it finds is to small once arrived a certain minimum, I guess once solved the less worrisome problem subsets.
Here I have a doubt. Has it a arrived to a local minimum too far from the real solution so that no proximity search may help to reduce it? (even though I can distance a lot from this minimum, but always from the same minimum, reducing the chances to find another set smaller than this one if it is too far).
If the answer is yes, I may have to consider find another different minimum.
I have to point out that I have noticed that by changing the pseudo-random seeds in the 150 variables instances, it definitely exceeds in grandeur the solving time (not waited till solved), meaning that it seems to be the case.
Further work be done. Stay tuned.
