On extremum-searching approximate probabilistic algorithms. (English) Zbl 0543.03029

The author proposes a simple probabilistic algorithm (similar to that of the Monte Carlo method) for an approximation of the maximum value of a recursive function defined on a finite set. It is shown, too, that if this function is regular or continuous in a sense, then its maximum value can be relatively approximated with a computational complexity which is substantially smaller than that of corresponding deterministic procedures.
Reviewer: V.Ja’kl


03D20 Recursive functions and relations, subrecursive hierarchies
03D15 Complexity of computation (including implicit computational complexity)
41A99 Approximations and expansions
65D99 Numerical approximation and computational geometry (primarily algorithms)
Full Text: EuDML


[1] A. V. Aho J. E. Hopcroft, J. D. Ullman: The Design and Analysis of Computer Algorithms. Reading, Addison-Wesley, London 1974 · Zbl 0326.68005
[2] M. O. Rabin: Probabilistic algorithms. Proceedings of the Symposium 1976, Carnegie-Mellon Univ., Pittsburgh, Academic Press, New York 1976, pp. 21 - 39. · Zbl 0384.60001
[3] I. Kramosil: Statistical verification procedures for propositional calculus. Computers and Artificial Intelligence 2 (1983), 3, 235-258. · Zbl 0529.68066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.