A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
✍ Scribed by Kazuhisa Makino; Toshihide Ibaraki‡
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 168 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 Ž Ž . . Ž . max F f denotes the set of minimal true vectors maximum false vectors of f. Ž Moreover, as the existence of a polynomial total time algorithm i.e., polynomial . time in the length of input and output for this problem is still open, we consider here a restricted problem: given an unknown positive function f of n variables, decide whether f is 2-monotonic or not, and if f is 2-monotonic, output both Ž . Ž . min T f and max F f . For this problem, we propose a simple algorithm, which is Ž 2 . based on the concept of maximum latency, and we show that it uses O n m time Ž 2 . < Ž .< < Ž .< and O n m queries, where m s min T f q max F f . This answers affirma-
tively the conjecture raised in Boros et al. Lecture Notes in Comput. Sci. 557 Ž . x w Ž . x 1991 , 104᎐115 , Boros et al. SIAM J. Comput. 26 1997 , 93᎐109 , and is an Ž 3 . improvement over the two algorithms discussed therein: one uses O n m time and Ž 3 . Ž 2 2 . Ž . O n m queries, and the other uses O nm q n m time and O nm queries.