{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T14:42:33Z","timestamp":1748788953058,"version":"3.37.3"},"reference-count":0,"publisher":"IOS Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"abstract":"<jats:p>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&amp;gt;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.<\/jats:p>","DOI":"10.3233\/978-1-60750-842-7-21","type":"book-chapter","created":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T11:58:24Z","timestamp":1740398304000},"source":"Crossref","is-referenced-by-count":1,"title":["On 2SAT-MaxOnes with Unbalanced Polarity: from Easy Problems to Hard MaxClique Problems"],"prefix":"10.3233","author":[{"family":"Argelich Josep","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"B&eacute;jar Ram&oacute;n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Fern&aacute;ndez C&egrave;sar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Mateu Carles","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","Artificial Intelligence Research and Development"],"original-title":[],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:00:33Z","timestamp":1740398433000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospressISSNISBN&issn=0922-6389&volume=232&spage=21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/978-1-60750-842-7-21","relation":{},"ISSN":["0922-6389"],"issn-type":[{"value":"0922-6389","type":"print"}],"subject":[],"published":{"date-parts":[[2011]]}}}