[NOTE: The following argument doesn't seem to work, but I'm leaving it here so others don't make the same mistake / in case someone can fix it. The issue is that an exponential lower bound on learning/identifying a monotone function, as below, does not necessarily contradict an incrementally polynomial algorithm for the problem. And it is the latter which is equivalent to checking the mutual duality of two monotone functions in poly time.]

I believe your conjecture on $\log N_X$ is false in general. If it is indeed the case that $\log N_X$ queries are needed, that implies quite a strong lower bound on learning monotone functions using membership queries. In particular, let the poset $X$ be the Boolean cube with the usual ordering (if you like, $X$ is the powerset of $\{1,...,n\}$ with $\subseteq$ as its partial order). The number $M$ of maximal antichains in $X$ satisfies $\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$ [1]. If your idea on $\log N_X$ is correct, then there is some monotone predicate on $X$ that requires essentially $\binom{n-1}{n/2} \approx 2^n$ queries. In particular, this implies a lower bound of essentially $2^n$ for the complexity of any algorithm solving this problem.

However, if I've understood correctly [which I now know I hadn't], your problem is equivalent to checking the mutual duality of two monotone functions, which can be done in quasi-polynomial time (see the intro of this paper by Bioch and Ibaraki, which cites Fredman and Khachiyan), contradicting anything close to a $2^n$ lower bound.

[1] Liviu Ilinca and Jeff Kahn. Counting maximal antichains and independent sets. arXiv:1202.4427

[NOTE: The following argument doesn't seem to work, but I'm leaving it here so others don't make the same mistake / in case someone can fix it. The issue is that an exponential lower bound on learning/identifying a monotone function, as below, does not necessarily contradict an incrementally polynomial algorithm for the problem. And it is the latter which is equivalent to checking the mutual duality of two monotone functions in poly time.]

I believe your conjecture on $\log N_X$ is false in general. If it is indeed the case that $\log N_X$ queries are needed, that implies quite a strong lower bound on learning monotone functions using membership queries. In particular, let the poset $X$ be the Boolean cube with the usual ordering (if you like, $X$ is the powerset of $\{1,...,n\}$ with $\subseteq$ as its partial order). The number $M$ of maximal antichains in $X$ satisfies $\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$ [1]. If your idea on $\log N_X$ is correct, then there is some monotone predicate on $X$ that requires essentially $\binom{n-1}{n/2} \approx 2^n$ queries. In particular, this implies a lower bound of essentially $2^n$ for the complexity of any algorithm solving this problem.

However, if I've understood correctly [which I now know I hadn't], your problem is equivalent to checking the mutual duality of two monotone functions, which can be done in quasi-polynomial time (see the intro of this paper by Bioch and Ibaraki, which cites Fredman and Khachiyan), contradicting anything close to a $2^n$ lower bound.

[1] Liviu Ilinca and Jeff Kahn. Counting maximal antichains and independent sets. arXiv:1202.4427

I'm not an expert in this area, but I believe your conjecture on $\log N_X$ is false in general. (If I'm right, it's still an interesting question as to what the correct measure of complexity is.)

If it is indeed the case that $\log N_X$ queries are needed, that implies quite a strong lower bound on learning monotone functions using membership queries. In particular, let the poset $X$ be the Boolean cube with the usual ordering (if you like, $X$ is the powerset of $\{1,...,n\}$ with $\subseteq$ as its partial order). The number $M$ of maximal antichains in $X$ satisfies $\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$ [1]. If your idea on $\log N_X$ is correct, then there is some monotone predicate on $X$ that requires essentially $\binom{n-1}{n/2} \approx 2^n$ queries. In particular, this implies a lower bound of essentially $2^n$ for the complexity of any algorithm solving this problem.

However, if I've understood correctly, your problem is equivalent to checking the mutual duality of two monotone functions, which can be done in quasi-polynomial time (see the intro of this paper by Bioch and Ibaraki, which cites Fredman and Khachiyan), contradicting anything close to a $2^n$ lower bound.

[1] Liviu Ilinca and Jeff Kahn. Counting maximal antichains and independent sets. arXiv:1202.4427

[NOTE: The following argument doesn't seem to work, but I'm leaving it here so others don't make the same mistake / in case someone can fix it. The issue is that an exponential lower bound on learning/identifying a monotone function, as below, does not necessarily contradict an incrementally polynomial algorithm for the problem. And it is the latter which is equivalent to checking the mutual duality of two monotone functions in poly time.]

I believe your conjecture on $\log N_X$ is false in general. If it is indeed the case that $\log N_X$ queries are needed, that implies quite a strong lower bound on learning monotone functions using membership queries. In particular, let the poset $X$ be the Boolean cube with the usual ordering (if you like, $X$ is the powerset of $\{1,...,n\}$ with $\subseteq$ as its partial order). The number $M$ of maximal antichains in $X$ satisfies $\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$ [1]. If your idea on $\log N_X$ is correct, then there is some monotone predicate on $X$ that requires essentially $\binom{n-1}{n/2} \approx 2^n$ queries. In particular, this implies a lower bound of essentially $2^n$ for the complexity of any algorithm solving this problem.

However, if I've understood correctly [which I now know I hadn't], your problem is equivalent to checking the mutual duality of two monotone functions, which can be done in quasi-polynomial time (see the intro of this paper by Bioch and Ibaraki, which cites Fredman and Khachiyan), contradicting anything close to a $2^n$ lower bound.

[1] Liviu Ilinca and Jeff Kahn. Counting maximal antichains and independent sets. arXiv:1202.4427