1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 27 '17 at 7:18
1
$\begingroup$

The problem MIN-3SAT is usually know as "minimum vertex cover for 3-uniform hypergraphs". Any reasonable algorithm that you will suggest will give a 3-approximation (or worse), and indeed, it is conjectured (and follows from the unique games conjecture) that no polynomial time algorithm can improve on this approximation ratio.

This means that if you try hard enough, it is extremely likely that you will find an instance in which your greedy approach gives a solution which is roughly 3 times as worse as the optimal solution. I'll let you find it on your own.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.