Abstract:
The complexity of exact learning of bounded-weight Boolean functions is considered in the paper using separately four types of queries: membership queries, equivalence queries, extended equivalence queries, and comparation queries. The values of the complexity for the first three types are obtained. Upper and lower bounds of the complexity for comparation queries being of the same order are presented. Moreover, the exact value of the complexity of learning upper bounded-weight Boolean functions with the help of comparation queries is obtained.
Fulltext:
PDF file (1124 kB)