# How can I identify that a restricted variant of Boolean SAT remains hard or not?

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.

• What is the problem you are trying to solve? Please specify it completely. You might also want to consult Schaefer's dichotomy theorem. Apr 27, 2014 at 5:08
• 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. Apr 27, 2014 at 5:28
• It seems that this cs.stackexchange.com/questions/11558/… answers your question. Even monotone formulas are hard by a reduction from dominating set. Apr 27, 2014 at 9:36
• @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. Apr 27, 2014 at 9:42

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