There is a correspondence between the gap in the probability of accepting positive instance and in the probability of accepting negative instance. This gap can be mapped into a gap between the optimal measure in the case of positive instance and the measure in the case of negative instance. You can see here the reduction f from the NP-complete decision problem SAT, such that if the original instance is satisfiable, then the value of the optimal solution is equal to the number of clauses of the new Boolean formula. While if the original instance is not satisfiable, then the number of clause we can satisfy in the new Boolean formula is at most the number of clauses in the formula divided by numbers greater then 1.

---