Maximizing the number of 'correct' literals in planar monotone 3SAT - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T18:54:57Z http://mathoverflow.net/feeds/question/57190 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57190/maximizing-the-number-of-correct-literals-in-planar-monotone-3sat Maximizing the number of 'correct' literals in planar monotone 3SAT Michael Biro 2011-03-03T01:07:25Z 2011-03-03T01:07:25Z <p>I'm trying to find the complexity of this optimization problem:</p> <p>Given an instance of planar monotone 3SAT, with positive clauses <code>\$C_i = v_{i1} V v_{i2} V v_{i3}\$</code> and negative clauses <code>\$D_i = not(w_{i1}) V not(w_{i2}) V not(w_{i3})\$</code>, (it's possible that <code>\$v_{ij} = w_{jl}\$</code> for some i,j,k,l), find the 0-1 assignment that maximizes the number of agreeing literals. Basically, maximize <code>\$(/sum_{C_i} v_{i1}+v_{i2}+v_{i3}) + (/sum_{D_i} 3 - w_{i1} - w_{i2} - w_{i3})\$</code>.</p> <p>Thanks</p>