Recursive problem

When the problem is equilibrated with the ratio of variable, clauses classified as hard, the possible solution bufurcate in exponential ratio.
For every variable, one option 0 or 1 bifurcates at least in two paths where 1/r of both paths are completely independent. The reason is you will have to explore 1/r  subset of solutions in one bifurcation totally independent from the other option.

In hard problems where clauses are rightly abundant and intermixed and solutions are a few, you are forced to explore (1+1/r)^num-vars different paths all completely independent.

That is one does not tell you anything about the other, still if is hard, probably only a few have solution. So it points to NP not P, at least without quantum computers domain.

It is true that you can apply some heuristics to search first the most promising paths, but if the few solutions are in different sides and well distributed, the mixed signals does not let you focus in one, but in the middle path that lets to nowhere. (In hard problems of course).

Example of heuristic, how many clauses and its size are left in every option. Less, looks better for a global minimum, but we have different global minimums, and it looks we want to go to all at a single ride, but they are completely at other extremes between them.

What would be lovely? Have a problem and that we could choose any unset variable and ask: if i set this to 0, will it be solvable? In case both said yes 0 and 1 would stop searching for one path just for the sake of focusing on one solution.

New achivement 400 variables

An improve in the search algorithm has now resulted in a fast execution

of hard problems of 400 variables.

It is worrisome that the next case of 500 variables is definitely not able to reduce

the entropy to 0. Somehow the problem is that it gets to solve a big part of a sub problem

very fast but this may not be the same path towards the global solution.

So I guess the simple of criteria of finding a low entropy may push the algorithm towards

great sub-solutions but not the global one. I guess I will have to find a way to consider

the viability of the chosen path by asking not solely how it is reducing the entropy but how

blocked it is becoming (meaning checking the entropy variance in every variable at its extremes).

Let's see what can we do.

Let's recognize, there must be a way otherwise we would not be reducing

constantly the time every year.

I have the intuition that it contains sub hard small problems inside a big one, like combine certain sub graphs in the exact combination.

This is the impression from the observation of how the entropy changed in the different stages during big hard problems search.

I'll keep posting.

Avoiding local minimums

The problem of local minimum detected in the last post has been improved

by widening the search (widening the random increases range) and by detecting deep minimums

with a timeout (seconds in the minimum).

This and a higher increase of the the inputs when escaping from bad circumstances (input set in which all input probabilities not assigned at 0 and 1 will increase the entropy no mater to what side we balance these inputs) has speed up the algorithm.

[1] [ Forced Satisfiable CSP and SAT Benchmarks of Model RB - A Simple Way for

Generating Hard Satisfiable CSP and SAT Formulas

http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm (frb30-15-cnf.tar.gz)]

First results: Method working with few variables

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.

[1] [Entropy_ (information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory)]

[2] [SATLib - benchmark problems http://people.cs.ubc.ca/~hoos/SATLIB/benchm.html]

First steps towards astonishing conclusions

Hi,

I am engineer researcher in Barcelona Autonomous University.

Having finishing my degree studies as a computer engineer and having

a fascination for the complexity field I have been involved for 10 months

in the research of an algorithm that helps to support strongly the conjeture

that N = NP. For those familiarized with the problem you can guess, I must have

created a SAT solver that I "think" it runs and works at a polynomial time.

Well, you guessed well. Now that "think" must be proved.

Right now my first steps are heading towards extend practice evaluations

with well know hard instances.

Though working now, I am reporting my results in the following weeks.

Stay tuned, you know science.