Geodesic
Instantaneously solvable search problems
Diskretnaya Matematika, Tome 8 (1996) no. 3, pp. 119-134 
È. È. Gasanov. Instantaneously solvable search problems. Diskretnaya Matematika, Tome 8 (1996) no. 3, pp. 119-134. http://geodesic.mathdoc.fr/item/DM_1996_8_3_a9/
@article{DM_1996_8_3_a9,
     author = {\`E. \`E. Gasanov},
     title = {Instantaneously solvable search problems},
     journal = {Diskretnaya Matematika},
     pages = {119--134},
     year = {1996},
     volume = {8},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1996_8_3_a9/}
}
TY  - JOUR
AU  - È. È. Gasanov
TI  - Instantaneously solvable search problems
JO  - Diskretnaya Matematika
PY  - 1996
SP  - 119
EP  - 134
VL  - 8
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_1996_8_3_a9/
LA  - ru
ID  - DM_1996_8_3_a9
ER  - 
%0 Journal Article
%A È. È. Gasanov
%T Instantaneously solvable search problems
%J Diskretnaya Matematika
%D 1996
%P 119-134
%V 8
%N 3
%U http://geodesic.mathdoc.fr/item/DM_1996_8_3_a9/
%G ru
%F DM_1996_8_3_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

We introduce a new class of algorithmic problems called the class of instantly solvable search problems. The problems of this class can be solved, in average, in a time needed to list the data forming the answer plus a constant independent of the dimension of the problem. Examples of instantly solvable search problems are given and the algorithms providing instant solutions are described.