On 2SAT-MaxOnes with Unbalanced Polarity: from Easy Problems to Hard MaxClique Problems
Josep Argelich, B eacute jar Ram oacute n, Fern aacute ndez C egrave sar, Carles Mateu · Frontiers in artificial intelligence and applications · 2011
We study the complexity of solving a variant of the Random 2SAT-MaxOnes problem, a variant created by introducing an additional parameter p to control the probability of having positive literals in the clauses of the problem instance, and show that its complexity pattern has interesting properties. This parameter p allows us to generate problem instances ranging from exceptionally hard optimization instances, when p=0, that are equivalent to MaxClique instances, to trivial problem instances when p=1. We show that our problem presents an easy-hard-easy complexity pattern, even on the hardest case of the problem (p=0) where instances are always feasible. We show that the hardness peak is mainly due to a sudden increase in the cost of finding the optimal solution and that for p>0 a phase transition from feasible to unfeasible instances appears, but with a lower hardness peak as p approaches to 1. We further investigate the reasons for such a peak, by analyzing the expected number of optimal solutions and expected number of variables set to 1 in optimal solutions.