Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
Endre Boros, Peter L. Hammer, Toshihide Ibaraki, Kazuhiko Kawakami · SIAM Journal on Computing · 1997
We consider the problem of identifying an unknown Boolean function f by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that f is a positive (or monotone) function of n variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in n and m, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of f. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function f of n variables, decide whether or not f is 2-monotonic and, if f is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries.