# monotone min 3-sat polynomial algorithm?

I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables x1,…,xnx1,…,xn (nn variables) and each literal is a positive appearance of a variable (no xi xi).

for example: (x1∨x3∨x7)∧(x5∨x4∨x2)(x1∨x3∨x7)∧(x5∨x4∨x2)

In other words: The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..). take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step. stop when no clauses left. it looks like this algo runs in O(m2n)O(m2n) time.

why isn't it an optimal algorithm?

UPDATE: Can someone give me an example to why the greedy algorithm won't give the optimal solution? I can't figure why the greedy approch is not good..

• Have you tried implementing it, and implementing a reference algorithm (e.g., one that uses brute force, or a SAT solver with pseudo-boolean constraints), and then tests it on a million randomly chosen small instances, to see if it always gives the right answer? If you try that I'm sure you'll find examples where your algorithm isn't optimal. – D.W. Jul 27 '17 at 7:18