Efficient Identification of Classes of P-Time Functions
Sandra Fontani (University of Siena, Italy)
We consider the problem of identifying a class of ptime functions in efficient time. We restrict our attention to particular classes of p-time functions, called uniform and we try to identify each function of such a class by guessing, after a small number of examples, some index for it or its next value. In both cases we introduce two efficient identification paradigms, called efficient and very efficient identification respectively. We find a characterization for efficient identification and, as a corollary, we show that the entire class P is not efficiently identifiable. A necessary condition is shown for very efficient identification, which becomes sufficient if and only if P = NP. We give some examples of well-known uniform classes which are very efficiently identifiable in both identification paradigms.
Keywords: learning theory