How can I identify that an instance of Boolean SAT problem 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 instance, not mentioned there, but I though of it, and searched, but could not find anything useful.

And the instance,

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 $X \subseteq Y$ satisfy $f$, too. What I want is finding the minimal $X$ where $f$ satisfies it, but not any $Z$ where $Z \subsetneq X$?

Is this problem still hard?

Clarification: Due to a comment, increasing is a term I used here, and the reason I used it is as follows. For a set of $n$ elements, its subsets can be represented by an $n$ bits register, the input to $f$. I assume that if $f(X) = 1$, then for any $Y$ such that $X \subseteq Y$, $f(Y) =1 $.

P.S. 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 hard.

Any help, even offers of search terms is appreciated.

Thanks in advance.

Answer 1

First of all, note that there may be more than one minimal $X$ satisfying $f(X) = 1$.

If we want to find just a single minimal $X$, then it can be done as follows.

Start with $S = \{x_1, \dots, x_n\}$. If $f(S) = 0$, then $f$ is identically $0$ and no minimal $X$ with $f(X) = 1$ exists. Otherwise, check $f(S \setminus \{ x_i \})$ for all $x_i \in S$. If there are all $0$, then $S$ is minimal with $f(S) = 1$. Otherwise, consider one such $x_i$ with $f(S \setminus \{ x_i \}) = 1$ and continue with $S \setminus \{ x_i \}$ instead of $S$.

Every step, you check at most $n$ elements (one less every step, but let's overestimate) and there are at most $n$ steps (because every step one element drops out of $S$). So this takes $n^2$ evaluations of $f$.

Answer 2

You still have to find such a subset of the inputs. Trivially, $f$ is increasing if $f(Y) = 1$ but for any $X \subset Y$ with $X \neq Y$ and $f(X) = 0$. This problem is just the standard SAT problem, so it is still NP-Complete. In practice, you may find many cases where you can check substantially fewer inputs. However, note that there are $2^{n}$ possible subsets, and $\sum_{i=0}^{n} \binom{|Y|}{i}$, for $n < |Y|$, will grow pretty quickly.

Also, even if you have the constraint that $X \subset Y$ (a proper subset) with $f(X) = 1$ implies that $f(Y) = 1$, you still have at most $2^{n} - 1$ possible subsets of $Y$ to check, as $\sum_{i=0}^{|Y|-1} \binom{|Y|}{i} = 2^{|Y|} - 1$.