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 $x_1,\dots,x_n$ ($n$ variables) and each literal is a positive appearance of a variable (no $~x_i$).
for example: $(x_1 \lor x_3 \lor x_7) \land (x_5 \lor x_4 \lor x_2)$
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(m^2n)$ time.
why isn't it not an optimal algorithm?
UPDATE: Sorry for the vague question, 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.
UPDATE 2: Can someone give me an example to why the greedy algorithm won't give the optimal solution? I read what rus9348 wrote but I still can't figure why the greedy approch is not good..