Efficient Identification of Classes of P-Time Functions
Дата
Авторы
Fontani,Sandra
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
learning theory