Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 8

available in:   PDF (256 kB) PS (92 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-08-0759


Efficient Identification of Classes of P-Time Functions

Sandra Fontani (University of Siena, Italy)


We consider the problem of identifying a class of pĀ­time 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

Categories: I.2.6