1
$\begingroup$

I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we have a boolean formula that is $0-valid$ then (of course) SAT problem is in $\mathcal{P}$ but finding a solution with maximum true literals is $\mathcal{NP}-$hard.

N.B. As defined in the previous papers, a $0-valid$ boolean formula $f$ is a boolean formula $f: \{0, 1\}^n\rightarrow\{0, 1\}$ that satisfies $f(0, \dotsc, 0)=1$.

My question is:

Can I represent a general $0-valid$ boolean formula on the variables $x=\left(x_1, \dotsc, x_n\right)$ by the following one:

$f(x)=\bigwedge\limits_{i=1}^{L}\bigvee\limits_{i\in\mathcal{S}_l}\neg\;x_i$?

Where $L$ is the number of clauses and $\mathcal{S}_l\;\forall\;l\in\{1,\dotsc, L\}$ is a subset of $\{1, \dotsc, n\}$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you please define what 0-valid means, to make your question self-contained? Are you asking if it can be representing in CNF using only negative literals (no positive literals)? $\endgroup$ – D.W.♦ Mar 5 '14 at 17:43
  • $\begingroup$ $0-valid$ is defined in the previous mentioned papers as follows: any boolean formula that is satisfied by a $0$ assignment. So if $f(x)$ is a boolean formula of $n$ variables, $f$ is $0-valid$ if $f(0)=1$. $\endgroup$ – npisinp Mar 5 '14 at 17:58
  • 2
    $\begingroup$ I suggest you edit the question to include this. People shouldn't need to read the comments or other links to understand the question. This is not a discussion forum; comments exist only to help you improve your question, and are transient, so important information needs to be in the question, not just in comments. $\endgroup$ – D.W.♦ Mar 5 '14 at 18:22
3
$\begingroup$

The constraints of a $0$-valid formula can be more general. All we know about them is that they are satisfied if all variables are $0$. For example, a constraint could be $x = y$ (i.e. $(x \land y) \lor (\lnot x \land \lnot y)$). Your form is not general enough, since it only considers constraints of the form $\lnot x_1 \lor \dots \lor \lnot x_\ell$.

While your formulation doesn't capture the problem of determining the most positive solution for a $0$-valid CSP, it is equivalent to an even more classical problem, set cover. In particular, your problem is NP-complete.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But can I say that under the formula that I gave, finding a maximum number of true literals is $\mathcal{NP}-$hard? since it is a conjunction of disjunction of variables (I can asume at least 3 variables per clause). $\endgroup$ – npisinp Mar 5 '14 at 17:43
  • 1
    $\begingroup$ Your problem is NP-complete, but for a different reason: it is equivalent to set cover. $\endgroup$ – Yuval Filmus Mar 5 '14 at 19:37
3
$\begingroup$

No. A formula in the form you propose has the property that it is never satisfied by the all-ones assignment (i.e., an assignment where all variables take the value True), assuming $L>0$. However, there exist non-trivial 0-valid formulas that don't have this property.

For instance, consider the xor $x \oplus y \oplus 1$; this is 0-valid, but is also satisfied by the all-ones assignment, and it is not equivalent to True, thus it cannot be expressed in the form you propose.

|cite|improve this answer
$\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.