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 almost always 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?


The reason that 3SAT is hardest empirically when the clause-to-literal ratio is 4.2 is because this is the satisfiability threshold (the threshold at which a random 3SAT becomes unsatisfiable with high probability). However, this is a very different type of hardness than NP-hardness. First of all, the model is different: you are generating a random 3SAT instance with a given clause-to-literal ratio, and hardness applies only on average. Second, there is no formal connection between the satisfiability threshold and computational hardness. There are some properties of the solution space which we think make the problem hard near the satisfiability threshold, but this is just a heuristic.

Now for your actual questions:

  1. While there are definitely no formal results, it might be the case that known practical approximation algorithms for MAX-3SAT perform poorly near the satisfiability threshold.

  2. No idea.

  3. You are asking two questions. Regarding your first question, if you had an algorithm which approximated MAX-3SAT only on satisfiable instances, say achieving 99% performance, you could run it on any given instance, and so determine whether it is satisfiable or less than 99% satisfiable. We know that this is unlikely as long as the performance is larger than 7/8. Regarding your second question, the instances coming out of the hardness proof are not arbitrary, so there is a class of formally "hard instances", but I don't think it has anything to do with the satisfiability threshold.

  • $\begingroup$ Thx. Herein lies what I have done. Generated few instances of 3SAT using <toughsat.appspot.com> and ran a crude/fast Approx. Algorithm on them (which I assume can be improved further). The results: <Lit Ct-Clause Ct-No. Of Unsatisfied Clauses> 50-500-31; 50-1000-87; 50-5000-488; 50-10000-1047; 100-1000-57 100-5000-479; 100-10000-1012; 250-2200-118; 2500-10000-910; 500-2200-81; 500-10000-796; The above generated ratio is greater than 7/8+e in all cases easily. Thus the query on 2 cases: 1. Hard cases of 3 SAT if SAT is satisfiable. 2. Hard cases of 3MaxSAT. $\endgroup$ – TheoryQuest1 May 4 '15 at 21:43
  • $\begingroup$ Thus I was wondering if I could have an idea about the difficult on average cases of Approximate 3SAT and Max3SAT to analyze if this Algorithm is useful in any way and benchmarking it further. $\endgroup$ – TheoryQuest1 May 4 '15 at 21:46

Regarding a test benchmark: Keep in mind that the 7/8 hardness result is about worst-case behavior, not average-case behavior.

Suppose you have an approximation algorithm for MaxSAT. The fraction of clauses your algorithm can satisfy might be different for each different input (i.e., for each SAT formula). The 7/8th hardness result says you should not expect your algorithm to satisfy more than 7/8ths of the clauses on all possible inputs. However, it might be easy to come up with an algorithm that, for many inputs, satisfies more than 7/8ths of the clauses. For instance, maybe you can satisfy 90% of the clauses for many or most inputs: that might be possible. But what you (probably) won't be able to do is achieve this for all inputs.

So, if you have an algorithm in mind, testing it on random inputs might not tell you very much about whether you've beat the hardness result you mention. As far I know, it seems possible that it might be easy to build an algorithm that, for a random input, on average satisfies more than 7/8ths of the clauses. This means that testing an algorithm on random inputs won't necessarily tell you very much. Even if you came up with some clever algorithm and found that, on random inputs, on average, the ratio of satisfied clauses is, say, 90%... that wouldn't contradict the NP-hardness results you mentioned. For these reasons, if you think you've got a great approximation algorithm that will do better than the hardness results suggest... it's not enough to test it on random inputs. You'd have to somehow test it on all possible inputs.

Or, to put it another way, the average fraction of clauses you can satisfy on random inputs might be very different from the guaranteed minimum fraction of clauses you can satisfy on all inputs.

  • $\begingroup$ Thanks for such a detailed reply. I do understand the idea. Thus I mentioned 'almost always difficult' for some approximation ratio or difficult on an average case benchmark set as testing on a random example would not reveal much. But I was unable to find and such result or data set for an Approximation Algorithm. $\endgroup$ – TheoryQuest1 May 5 '15 at 6:40
  • $\begingroup$ @TheoryQuest1, OK, good, glad this makes sense -- and sorry to repeat something that was already evident to you. $\endgroup$ – D.W. May 5 '15 at 6:43

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.