Abstract
Learning from examples in the presence of overwhelmingly many irrelevant variables has been studied in the field of machine learning theory, where the learner is required to derive as succinct hypotheses as possible. In this paper, we consider the following computational learning problem: Given a set of negative examples in n Boolean variables, the learner is required to find O(log n) relevant variables whose conjunction gives a consistent hypothesis. This problem belongs to a complexity class called β~2~. We prove that this problem is equivalent, by probabilistic log‐space Turing reduction, to the problem of finding satisfiable assignments for polynomial‐size ${\bf \Pi}^{0}_{3}$‐circuits with O(log^2^ n) inputs. As a consequence, we can show that learning of O(log n)‐length Boolean conjunctions from negative examples is neither β~2~‐hard unless P ⊆ POLYLOG‐SPACE, nor polynomial‐time computable unless NP ⊆ DTIME(2^O(√n)^).
In this paper, we also discuss the polynomial‐time learnability of an O(log n)‐length monotone Boolean conjunction from negative examples, when the examples are drawn from the uniform distribution. © 2001 Scripta Technica, Syst Comp Jpn, 33(1): 1–7, 2002