The maximum latency and identification of positive Boolean functions

Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean function f by using membership queries only, where min T(f)(maxF(f)) denotes the set of minimal true vectors (maximal false vectors) of S. It is known that an incrementally polynomial algorithm exists if and only if there is a polynomial time algorithm to check the existence of an unknown vector u for given sets MT subset of or equal to minT(f) and MF subset of or equal to maxF(f); that is, u is an element of {0, 1}(n) \({v \ v greater than or equal to w for some ut is an element of MT} boolean OR (v \ v w for some w is an element of MF}). This paper introduces a measure for the difficulty to find an unknown vector, which is called the maximum latency. If the maximum latency is constant, then an unknown vector can be found in polynomial time and there is an incrementally polynomial algorithm for identification. Several subclasses of positive functions are shown to have constant maximum latency, e.g., 2-monotonic positive functions, Delta-partial positive threshold functions, and matroid functions, while the class of general positive functions has right perpendicular n/4left perpendicular + 1 maximum latency and the class of positive k-DNF functions has Omega(root n) maximum latency.