There is an explicit counterexample to my proposal for polynomial complexity solution to max-cut problem (see The P-versus-NP page entry #63 ):

The quartic polynomial is positive definite, e.g > 0 for all x, but cannot be represented as a sum of squares. On the other hand, this polynomial represent fully connected graph. The polynomial is due to Pablo Parrilo via Amir Ali Ahmadi.

### Like this:

Like Loading...

*Related*