informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-441Research ArticleСТАТЬИ ПО МАТЕРИАЛАМ КОНФЕРЕНЦИЙARTICLES ON THE MATERIALS CONFERENCEЛогическая характеризация класса сложности задач, разрешимых вероятностными алгоритмами за полиномиальное времяLogical characterization of complexity class of problems solvable by probablistic algorithms in polynomial timeНайденкоВ. Г.NaidenkoV. G.

Ведущий научный сотрудник Отдела комбинаторных моделей и алгоритмов, канд. физ-мат. наук

Vladimir G. Naidenko - Cand. Sci. (Phys.-Math.), Leading Researcher of the Department of Combinatorial Models and Algorithms.

11, Surganova Str., 220072, Minsk

naidenko@im.bas-net.byИнститут математики, Национальная академия наук БеларусиInstitute of Mathematics, National Academy of Sciences of Belarus20181209201815499101Copyright © Найденко В.Г., 20182018Найденко В.Г.Naidenko V.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/441

Рассмотрена проблема описания класса вычислительной сложности BPP (от англ. bounded-error probablistic polynomial time) в терминах логического языка. BPP представляет собой класс вычислительных проблем в распознавательной постановке, которые эффективно решаются с помощью вероятностных машин Тьюринга за полиномиальное время. Класс BPP имеет важное прикладное значение, поскольку включает в себя самый широкий спектр практических проблем, которые могут быть быстро решены на современных компьютерах. В то же время до сих пор считалось, что BPP невозможно логически охарактеризовать ввиду семантических ограничений, наложенных на вероятностные машины Тьюринга, которые распознают языки в BPP. Используя новый метод характеристических множеств, в работе впервые получена логическая характеризация класса BPP в виде разрешимого фрагмента логики второго порядка.

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.

теория моделейвычислительная сложностьдескриптивная сложностьлогическая характеризацияметод характеристических множествmodel theorycomputational complexitydescriptive complexitylogical characterizationmethod of characteristic setsИнститут математики НАН БеларусиReferencesFagin, R. Generalized first-order spectra and polynomial-time recognizable sets / R. Fagin // Complexity of Computation, SIAM-AMS Proceedings. - 1974. - Vol. 7. - P. 27-41.Fagin R. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, SIAM-AMS Proceedings, 1974, vol. 7, pp. 27-41.Stockmeyer, L. The polynomial-time hierarchy / L. Stockmeyer // Theoretical Computer Science. - 1977. -Vol. 3. - P. 1-22.Stockmeyer L. The polynomial-time hierarchy. Theoretical Computer Science, 1977, vol. 3, pp. 1-22.Naidenko, V. Logics for complexity classes / V. Naidenko // Logic Journal of the IGPL. - 2014. - Vol. 22, по. 6. -P. 1075-1093.Naidenko V. Logics for complexity classes. Logic Journal of the IGPL, 2014, vol. 22, no 6, pp. 1075-1093.Immerman, N. Descriptive Complexity / N. Immerman. - Springer, 1998. - 250 p.Immerman N. Descriptive Complexity. Springer, 1998, 250 p.

The authors declare that there are no conflicts of interest present.