monotone min-3-sat polynomial algorithm?

Question

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..

Answer 1

3SAT is NP-complete. Positive 3SAT (where all literals are positive) is in P, and thus presumably not NP-complete. There is an even simpler algorithm for Positive 3SAT: set all variables to true. That will always provide a satisfying assignment.

I can't comment on your algorithm because it doesn't seem fully specified: you describe what order to make assignments to variables, but you don't describe how to choose a truth assignment for each variable. (Should it be set to true? to false? The question doesn't say.)

Answer 2

answer to update 2: take this example

$(x_1,x_2,x_4), (x_1,x_2,x_5), (x_1,x_3,x_4), (x_1,x_3,x_5), (x_3), (x_2)$

By greedy, you will have 3 literals to set to true - $x_1, x_2, x_3$. But optimal answer is - $x_2, x_3$.

The greedy approach does not work, because when you removing bigger number of clause, may be you are removing clauses for optimal choices.

If you are trying to derive a heuristic, you can try next level of heuristic as instead of choosing only one maximum variable, you can choose two variables which cover most of the clauses. but it still won't be optimal, because it is not considering three variables which together cover most of the clauses.

If you are considering k literals with most appearance, the complexity would be, $O(m^2\binom{n}{k})$. So if you are trying for each possible $k$, total complexity would be $O(m^2 \sum \binom{n}{k}) = O(2^n)$. So the exponential factor comes!

By the way, this was a very intuitive argument. Formally, one would reduce Dominating Set problem to this one - as described in link provided by @rus9384.