Complexity results for the gap inequalities for the max-cut problem