3
$\begingroup$

While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this variant (not mentioned there, but I though of it) and searched, but could not find anything useful.

Consider this variant:

Suppose $f$ is a boolean function in $n$ boolean variables, but with this extra property, that $f$ is increasing. I have thought of $n$ boolean variables, $X_1, \ldots, x_n$ as representation of subsets of a set with $n$ elements, and if some subset like $X$ satisfies $f$, then all $Y$ s.t. $X \subseteq Y$ satisfy $f$, too. What I want is finding the collection of all minimal $X$ where $f$ satisfies each of them, but not any $Z$ where $Z \subsetneq X$?

Is this problem still hard?

If I consider the $x_1, \ldots, x_n$ as a number, then increasing property of $f$ helps solving it in polynomial time, just a binary search suffices! So, I made it a little bit harder.

Any help, even offers of search terms is appreciated.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What is the problem you are trying to solve? Please specify it completely. You might also want to consult Schaefer's dichotomy theorem. $\endgroup$ – Yuval Filmus Apr 27 '14 at 5:08
  • $\begingroup$ Thanks for your tip, it is of a great help. The problem is as stated, it is a theoretical curiosity, we have a boolean function $f$ in $n$ variables, and we want to find the smallest $X$ such that its binary representation as $x_1 , \ldots , x_n$ satisfies $f$, with this in mind that $f$ is increasing, a term I use, is the problem still NP-hard? I think it is, but I cannot do the reduction since of this bothering increasing nature. By the way, your comment helps and I was introduced to some thing new. $\endgroup$ – Ali Shakiba Apr 27 '14 at 5:28
  • 1
    $\begingroup$ It seems that this cs.stackexchange.com/questions/11558/… answers your question. Even monotone formulas are hard by a reduction from dominating set. $\endgroup$ – Andrej Bauer Apr 27 '14 at 9:36
  • $\begingroup$ @AndrejBauer Thanks for the link, I shall think more about applying the method there to this instance. I will post it if I've found a proof. $\endgroup$ – Ali Shakiba Apr 27 '14 at 9:42
5
$\begingroup$

Your problem cannot be solved in polynomial time, for a boring reason: the size of the output might be exponential in the time of the input. Therefore, there is no hope for a polynomial-time algorithm.

For instance, consider the boolean function $f:\{0,1\}^n \to \{0,1\}$ that outputs $1$ if its input vector has at least $n/2$ ones (i.e., its Hamming weight is at least $n/2$), and $0$ otherwise. This function can be represented by a polynomial-size monotone formula. However, there are exponentially many minimal $x$ such that $f(x)=1$. In particular, each $x$ of Hamming weight $n/2$ is such a minimal input, and there are ${n \choose n/2} \approx 2^n/\sqrt{n}$ such inputs.

So, there's no hope.

As Andrej Bauer points out, a related problem (testing whether there exists an input of Hamming weight at most $k$ that causes the boolean function to output $1$) is also NP-complete; see Prove NP-completeness of deciding satisfiability of monotone boolean formula.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for both the reasoning and the link provided at the end of the answer. That's right. $\endgroup$ – Ali Shakiba Apr 28 '14 at 6:34

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.