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.

  • $\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$ Apr 27, 2014 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$ Apr 27, 2014 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$ Apr 27, 2014 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$ Apr 27, 2014 at 9:42

1 Answer 1


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.

  • $\begingroup$ Thanks for both the reasoning and the link provided at the end of the answer. That's right. $\endgroup$ Apr 28, 2014 at 6:34

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.