6533b821fe1ef96bd127b75c

RESEARCH PRODUCT

Optimization problem in inductive inference

Andris Ambainis

subject

CombinatoricsOptimization problemFinInductive probabilitySubroutineTotal functionFunction (mathematics)Inductive reasoningUpper and lower boundsMathematics

description

Algorithms recognizing to which of n classes some total function belongs are constructed (n > 2). In this construction strategies determining to which of two classes the function belongs are used as subroutines. Upper and lower bounds for number of necessary strategies are obtained in several models: FIN- and EX-identification and EX-identification with limited number of mindchanges. It is proved that in EX-identification it is necessary to use n(n−1)/2 strategies. In FIN-identification [3n/2 − 2] strategies are necessary and sufficient, in EX-identification with one mindchange- n log2n+o(n log2n) strategies.

yearjournalcountryeditionlanguage
1995-01-01
https://doi.org/10.1007/3-540-60217-8_6