The problem is as follow:

we have n variables x_1, x_2, ... x_n

and m triples t_1, t_2, ... t_m

each triple contain three distinct variables for example t_1 = {x_1, x_3, x_5}

An assignment is to assign all variables value either 0 or 1. An triple is called active if all variables has the same value. say if t_1 = {x_1, x_3, x_5} and the assignment assigns x_1 x_3 and x_5 value of 0 then t_1 is active.

Then we need to find a assignment to minimize the number of active triples.

I can think about an non polynomial time algorithm that is to start from an arbitrary assignment and then start to check from x_1 to x_n. if we flip x_k it leads to a less number of active triples then we do it and start to check from the beginning again. It ends when we can not flip any x_k.

But there should be an polynomial time algorithm for this problem. Can anyone help me with this? Thanks in advance!!