Almost all monotone Boolean functions are polynomially learnable using membership queries

被引：8

作者：

Shmulevich, I

Korshunov, AD

Astola, J

机构：

[1] Tampere Univ Technol, Tampere Int Ctr Signal Proc, FIN-33101 Tampere, Finland

[2] Sobolev Inst Math, Novosibirsk, Russia

来源：

INFORMATION PROCESSING LETTERS | 2001年 / 79卷 / 05期

关键词：

monotone Boolean function; learning; membership query; computational complexity;

D O I：

10.1016/S0020-0190(00)00225-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider exact learning or identification of monotone Boolean functions by only using membership queries. It is shown that almost all monotone Boolean functions are polynomially identifiable in the input number of variables as well as the output being the sum of the sizes of the CNF and DNF representations. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：211 / 213

页数：3

共 7 条

[1] NEGATIVE RESULTS FOR EQUIVALENCE QUERIES [J].