1
$\begingroup$

1.Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP.

2.Its also experimentally known that 3SAT has the most difficult known cases when the clause to literal ratio is approximately 4.2.

Q1. Is there a similar result for 3MaxSAT where the approximation algorithm for satisfying some 7/8+e of clauses becomes on Average difficult if 3MaxSAT has some specific format (like 3SAT in 2.) ?

Q2. Is there a benchmark set available for 3MaxSAT approximation algorithms for such cases?

Q3. Is there a similar approximation hardness result for 3SAT (like 3MaxSAT in 1.) if informed that the given 3SAT is satisfiable? Is just the clause to literal ratio is sufficient to represent completely the hardest cases for such approximation algorithms too?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Be patient: you asked this just a day ago. As far as votes, the question might be better-received if you followed the advice at cstheory.stackexchange.com/help/how-to-ask and cstheory.stackexchange.com/help/on-topic -- what research have you done? What have you tried? Have you tried doing some of those same experiments yourself? Have you tried doing a literature search? What are your thoughts? Also, generally, I'd encourage you to ask just one question per question. $\endgroup$ – D.W. May 30 '15 at 16:24
  • $\begingroup$ I tried searching for any relevant literature, but was unable to get any explicit algorithm/methods to generate such cases.. the proof is essentially existential in nature.. thanks for the advice.. agreed but they are essentially interlinked.. $\endgroup$ – TheoryQuest1 May 30 '15 at 16:54
  • $\begingroup$ Cross-posted on CS.SE: cs.stackexchange.com/q/42146/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Apr 21 '17 at 5:40
  • $\begingroup$ That question was posted about 2 years ago! Though i do understand. $\endgroup$ – TheoryQuest1 Apr 22 '17 at 12:35