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 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>