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?
Difficult On Average Cases for 3MaxSAT and 3SAT Approximation Algorithm
cc.complexity theory;approximation algorithms