1
$\begingroup$

I'm trying to find the complexity of this optimization problem:

Given an instance of planar monotone 3SAT, with positive clauses $C_i = v_{i1} V v_{i2} V v_{i3}$ and negative clauses $D_i = not(w_{i1}) V not(w_{i2}) V not(w_{i3})$, (it's possible that $v_{ij} = w_{jl}$ for some i,j,k,l), find the 0-1 assignment that maximizes the number of agreeing literals. Basically, maximize $(/sum_{C_i} v_{i1}+v_{i2}+v_{i3}) + (/sum_{D_i} 3 - w_{i1} - w_{i2} - w_{i3})$.

Thanks

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It should be polynomial time to maximize the given sum. Add both sums together and find which literals occur negatively more often than positively, and vice versa. Unless you meant something else? Gerhard "Ask Me About System Design" Paseman, 2011.03.02 $\endgroup$
    – Gerhard Paseman
    Commented Mar 3, 2011 at 1:12
  • 1
    $\begingroup$ If you ask for an assignment for which the instance evaluates to 1, it is probably something like #P-hard to get one and maximize the sum as well. Gerhard "Ask Me About System Design" Paseman, 2011.03.02 $\endgroup$
    – Gerhard Paseman
    Commented Mar 3, 2011 at 1:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .