For which $c, d$ is $Gap2SAT[c, d]$ in $P$ (such that $0<c<d<1$)?
(I know if d=1 then for each c it will be in P, however with which c,d such that $0<c<d<1$ can I simply return YES?)
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Assuming the Unique Games Conjecture, your problem is solved for MAX-CUT in Ryan O'Donnell and Yi Wu, An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests, who determined the gap curve for this problem.
I am not aware of any such work for MAX-2SAT, but Per Austrin has essentially determined the optimal approximation ratio (again, assuming the Unique Games Conjecture) in his paper Balanced MAX 2-SAT might not be the hardest.
In celebrated work, Prasad Raghavendra has essentially determined the optimal approximation ratio for any constraint-satisfaction problem, again assuming the Unique Games Conjecture.