Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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 –  Gerhard Paseman Mar 3 '11 at 1:12
1  
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 –  Gerhard Paseman Mar 3 '11 at 1:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.