Tell HN: A beautiful idea (that didn't work) for solving 3SAT

In 3SAT, the boolean satisfiablility problem, you have n variables, which are booleans. You have a bunch of clauses, each of which are the OR of three variables (or their negations). For a valid solution, you need to find values of the variables that make each of the clauses true.

My approach was as follows: If true = 1 and false = 0, then a AND b = ab (that is, normal numerical multiplication), and a OR b = a + b - ab (using normal numerical addition and subtraction), and NOT a = 1 - a Using these, you can define a monster function that is the AND of all the clauses, each of which is the OR of three variables or their negations. This function is a purely arithmetic function - there are no boolean operations, only arithmetic ones.

Now you can replace the boolean variables with real ones on the closed interval [0, 1]. Instead of being restricted to the vertices of the n-dimensional cube defined by the variables, we can now start in the interior of it, and follow the gradient of the function to find the solution. Even better, we can do so in polynomial time!

I really like this idea, but it didn't work. It turns out that the function is too complicated for a simple gradient follower to solve - it has maxima inside the volume.

Well, I still think that it was an interesting idea...