Reflections on SDG and the P=NP problem

SDG has an interesting connection to the famous P=NP problem.
You can earn one million dollars if you solve it ;-)
http://www.claymath.org/millennium/P_vs_NP/

The optimal price for many of the derivatives separates 
P from NP-complete in the following sense.

Each predicate pred has an optimal price opt(pred).
opt(pred) is the fraction of constraints that can be satisfied
in any CSP formula satisfying pred.
We consider predicates that are defined by 
a set of Boolean relations.
What is interesting is that for most predicates pred,
the set of CSP formulas satisfying pred and satisfying the fraction
opt(pred) + e, for any positive but arbitrary small e,
is an NP-complete set.

Therefore the optimal derivative prices have a deeper meaning
in classifying computational problems.

If you want more info on this, read:
http://www.ccs.neu.edu/research/demeter/biblio/maxmean.html
and the newer paper:
http://www.ccs.neu.edu/research/demeter/biblio/local-search-eg.html