Using Church for Partial Satisfaction:

Given a weighted CSP formula S, and a fraction t in [0,1], 
generate an assignment
satisfying the fraction t of the clauses.

What I expect:

For some S, t it will be very fast.
For others it will be very slow.