3SAT can be translated into continuous global optimization of polynomial

[Jarek Duda]

In 3SAT problems we have to valuate variables to fulfill all
alternatives of triples of these variables or their negations – look
that (x OR y) can be changed into optimizing

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

and analogously seven terms for alternative of three variables.
Finding global minimum of sum of such polynomials for all terms, would
solve our problem. (from www.scienceforums.net/topic/49246-four-dimensional-understanding-of-quantum-computers/
)
Introducing one additional variable per term(v), we can lower
polynomial degree from 14 to 8:
x OR y OR z =
[(v AND (x OR y)) OR (not(v) AND not(x) AND not(y))]
AND (v OR z)
Maybe we get lower by adding (polynomially) more variables?

I’ve seen such approaches which needed fulfilling constrains (
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.726&rep=rep1&type=pdf
), but we see that NP problems can be translated into just finding
minimum of degree 8 (or less) real nonnegative polynomial.
It's going out of standard combinatorial techniques to continuous
world of numerical analysis: using gradient methods, local minims
removing methods, evolutionary algorithms ... it's completely
different realm.

There are some approaches to prove P!=NP - they would have to cover
also these completely different continuous approaches.
But how to even calculate complexity of such complex continuous
optimization problems?

[Patricia Shanahan]

Jarek Duda wrote:
...

> I’ve seen such approaches which needed fulfilling constrains (
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.726&rep=rep1&type=pdf
> ), but we see that NP problems can be translated into just finding
> minimum of degree 8 (or less) real nonnegative polynomial.
> It's going out of standard combinatorial techniques to continuous
> world of numerical analysis: using gradient methods, local minims
> removing methods, evolutionary algorithms ... it's completely
> different realm.

...

Integer Programming is NP-hard, and its decision form is NP-complete.
The corresponding continuous optimization problem, Linear Programming in
rational numbers, has a polynomial time algorithm.

You can't always exactly solve IP by reduction to LP because the result
of truncating the LP solution to integers can either reduce the value of
the objective function below the value it would have for some other
integer solution or break at least one constraint.

What is different about this reduction of 3SAT to continuous
optimization? How do you translate the result of the continuous
optimization back to booleans such that all constraints will be met?

Patricia

[Jarek Duda]

In thess simple looking methods we don't have any constrains, we don't
need practically any truncations - the nonnegative real polynomial is
constructed so that it's zero iff all terms are fulfilled - if its
global minimum is zero the answer is 'true' (all variables have to be
0 or 1), else 'false' (in other minimals variables are somewhere
between).

We just need to minimalize polynomial (of e.g. 8 degree) - the
question is if required time has to grow exponentially with the number
of variables ...
In the linked article there is suggested that it grows slower - but
it's made for randomly generated 3SATs - the real question is what
about pessimistic situations - really hard 3SAT problems?

Jarek
webpage: http://tcs.uj.edu.pl/jarek