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?)

  • $\begingroup$ What is Gap2SAT? $\endgroup$ – xskxzr Nov 3 '18 at 4:02

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.