Logical characterization of complexity class of problems solvable by probablistic algorithms in polynomial time
Abstract
A problem to describe the complexity class BPP in terms of a logical language is considered. BPP (abbreviation for bounded-error probablistic polynomial time) represents the class of computational decision problems that are efficiently solvable in polynomial time. The class BPP has an important practical significance since as it includes the largest spectrum of applied problems. At the same time till now, it was supposed that BPP cannot be characterized because of semantic constraints imposed on Turing machines recognizing languages in BPP. Using a new method of characteristical sets we are the first to provide a logical characterization of the class BPP as a decidable fragment of the second-order logic.
About the Author
V. G. Naidenko
Institute of Mathematics, National Academy of Sciences of Belarus
Belarus
Belarus
Vladimir G. Naidenko - Cand. Sci. (Phys.-Math.), Leading Researcher of the Department of Combinatorial Models and Algorithms.
11, Surganova Str., 220072, Minsk
References
1. Fagin R. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, SIAM-AMS Proceedings, 1974, vol. 7, pp. 27-41.
2. Stockmeyer L. The polynomial-time hierarchy. Theoretical Computer Science, 1977, vol. 3, pp. 1-22.
3. Naidenko V. Logics for complexity classes. Logic Journal of the IGPL, 2014, vol. 22, no 6, pp. 1075-1093.
4. Immerman N. Descriptive Complexity. Springer, 1998, 250 p.
Review
For citations:
Naidenko V.G. Logical characterization of complexity class of problems solvable by probablistic algorithms in polynomial time. Informatics. 2018;15(4):99-101. (In Russ.)
Views: 617
Email this article 