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

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

<p>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.) ?</p>

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

<p>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?</p>

CC BY-SA 3.0
2015-05-30T16:24:16.600Z
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 http://cstheory.stackexchange.com/help/how-to-ask and http://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.
D.W.
CC BY-SA 3.0
2015-05-30T16:54:41.243Z
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..
TheoryQuest1
CC BY-SA 3.0
2017-04-21T05:40:59.823Z
Cross-posted on CS.SE: https://cs.stackexchange.com/q/42146/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
CC BY-SA 3.0
2017-04-22T12:35:32.267Z
That question was posted about 2 years ago! Though i do understand.
TheoryQuest1
<cc.complexity-theory><approximation-algorithms>
Difficult On Average Cases for 3MaxSAT and 3SAT Approximation Algorithm
TheoryQuest1
# Difficult On Average Cases for 3MaxSAT and 3SAT Approximation Algorithm

(Asked by: username_0 on 2015-05-29)

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?

**Tags:** cc.complexity-theory, approximation-algorithms

> **Comments:**
> **username_1**: 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 http://cstheory.stackexchange.com/help/how-to-ask and http://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.  
> **username_0**: 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..  
> **username_1**: Cross-posted on CS.SE: https://cs.stackexchange.com/q/42146/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  
> **username_0**: That question was posted about 2 years ago! Though i do understand.  

---

## 0 answers

