POLYNOMIAL-TIME RECOGNITION OF 2-MONOTONIC POSITIVE BOOLEAN FUNCTIONSGIVEN BY AN ORACLE

We consider the problem of identifying an unknown Boolean function f b y asking an oracle the functional values f(a) for a selected set of te st vectors a is an element of {0, 1}n. Furthermore, we assume that f i s a positive (or monotone) function of n variables. It is not yet know n whether or not the whole task of generating test vectors and checkin g 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) (resp ectively, max F(f)) denotes the set of minimal true (respectively, max imal false) vectors of f. To partially answer this question, we propos e 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 firs t algorithm uses O(nm(2) + n(2)m) time and O(nm) queries, while the se cond one uses O(n(3)m) time and O(n(3)m) queries.