STRUCTURAL-ANALYSIS OF POLYNOMIAL-TIME QUERY LEARNABILITY

In this paper we study the computational power of polynomial-time quer y learning systems for several query types, and the computational comp lexity of a ''learning problem'' for several representation classes. A s corollaries of our results, we prove some polynomial-time nonlearnab ility results, and relate polynomial-time learnability of some represe ntation classes to the complexity of representation finding problems o f P/poly oracles. For example, for CIR, a representation class' by log ical circuits, it is shown that P(NP1()) is an upper bound of power of query learning systems for CIR, and that P(NP1()) is also a lower bou nds of power of query learning systems for CIR when they are used to l earn a certain subclass R of CIR. It is also shown that the problem of learning CIR is P(NP(NP1()))-solvable. Then, using these results, the following relations are proved: (1) If, for some A is-an-element-of P /poly, the representation finding problem of A is not in P(NP1A), then CIR is not polynomial-time query learnable even by using queries such as membership, equivalence, subset, superset, etc. (2) On the other h and, if the above-mentioned subclass R of CIR is not polynomial-time q uery learnable by using subset and superset queries, then some B is-an -element-of P/poly exists such that its representation finding problem is not in P(NP1B).