2
$\begingroup$

Consider a CNF formula $F$ such that all the literals in every clause must be negative ( here is an example : $F$ = ($\bar{x_{1}}$ $\wedge$ $\bar{x_{2}}$) $\vee$ ($\bar{x_{3}}$ $\wedge$ $\bar{x_{4}}$ $\wedge$ $\bar{x_{5}}$) would be a valid formula where as $F$ = ($x_{1}$ $\vee$ $\bar{x_{3}}$ ) would not be a valid formula $F$ . It is known that this type of formula is satisfiable given you can set every variable to 0 , which will satisfy all the clauses . However, what if you received a positive integer $i$ and were asked if you could assign at most $i$ variables to a value of 0.

I know $F$ would still be satisfiable, and I know this would be NP-Complete. However, I am having difficulty reducing set cover to this problem in order to prove NP-completeness. I know that there being negations everywhere would result in the same number ( but inverted ) of truth assignments that would lead to satisfiability compared to if there were not any in the first place. Maybe trying to reduce set-cover to this problem is a dead end? Let me know what you think.

$\endgroup$

1 Answer 1

1
$\begingroup$

The choice of set cover might not be ideal. Let us rephrase the problem. You get a set of $m$ cluases $C_1, \dots C_m$ each consists of negative variables only. You need to find a set of $k$ variables that intersects each of these clauses (the variables that you would assign the value $0$. Clearly this corresponds to the hitting set problem defined as follows:

The hitting set problem

Given a family of $m$ sets $\mathcal{F} = \{S_1, \dots S_m\}$ over a ground set $U$. Is there a set of at most $k$ elements that have a non empty intersection with each of the sets in $\mathcal{F}$.

This problem is also NP-complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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