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

Question

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.

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.