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

摘要

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 is an element of {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. [References: 26]