Efficient Identification of Classes of P-Time Functions
| dc.creator | Fontani,Sandra | |
| dc.date | 2000 | |
| dc.date.accessioned | 2024-02-06T12:50:45Z | |
| dc.date.available | 2024-02-06T12:50:45Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-006-08-0759 | |
| dc.identifier | https://lib.jucs.org/article/27705/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/7799 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 6(8): 759-780 | |
| dc.subject | learning theory | |
| dc.title | Efficient Identification of Classes of P-Time Functions | |
| dc.type | Research Article |