Finding the Relationship between a Search Algorithm and a Class of Functions on Discrete Space by Exhaustive Search

* The work is supported by RFBR, grant 04-01-00858-a.

The task of revealing the relationship between a search algorithm and a class of functions those it solves is considered. Particularly, there was found a class of functions solvable by some adaptive search algorithm for a discrete space of low cardinality. To find an optimal algorithm exhaustive search was used. Algorithm quality criterion based on equivalence classes was also introduced.