((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?
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
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