Логическая характеризация класса сложности задач, разрешимых вероятностными алгоритмами за полиномиальное время
Аннотация
Рассмотрена проблема описания класса вычислительной сложности BPP (от англ. bounded-error probablistic polynomial time) в терминах логического языка. BPP представляет собой класс вычислительных проблем в распознавательной постановке, которые эффективно решаются с помощью вероятностных машин Тьюринга за полиномиальное время. Класс BPP имеет важное прикладное значение, поскольку включает в себя самый широкий спектр практических проблем, которые могут быть быстро решены на современных компьютерах. В то же время до сих пор считалось, что BPP невозможно логически охарактеризовать ввиду семантических ограничений, наложенных на вероятностные машины Тьюринга, которые распознают языки в BPP. Используя новый метод характеристических множеств, в работе впервые получена логическая характеризация класса BPP в виде разрешимого фрагмента логики второго порядка.
Ключевые слова
теория моделей,
вычислительная сложность,
дескриптивная сложность,
логическая характеризация,
метод характеристических множеств
При поддержке: Институт математики НАН Беларуси
Об авторе
В. Г. Найденко
Институт математики, Национальная академия наук Беларуси
Беларусь
Ведущий научный сотрудник Отдела комбинаторных моделей и алгоритмов, канд. физ-мат. наук
Беларусь
Ведущий научный сотрудник Отдела комбинаторных моделей и алгоритмов, канд. физ-мат. наук
Список литературы
1. Fagin, R. Generalized first-order spectra and polynomial-time recognizable sets / R. Fagin // Complexity of Computation, SIAM-AMS Proceedings. - 1974. - Vol. 7. - P. 27-41.
2. Stockmeyer, L. The polynomial-time hierarchy / L. Stockmeyer // Theoretical Computer Science. - 1977. -Vol. 3. - P. 1-22.
3. Naidenko, V. Logics for complexity classes / V. Naidenko // Logic Journal of the IGPL. - 2014. - Vol. 22, по. 6. -P. 1075-1093.
4. Immerman, N. Descriptive Complexity / N. Immerman. - Springer, 1998. - 250 p.
Рецензия
Для цитирования:
Найденко В.Г. Логическая характеризация класса сложности задач, разрешимых вероятностными алгоритмами за полиномиальное время. Информатика. 2018;15(4):99-101.
For citation:
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.)
Просмотров: 533
Послать статью по эл. почте 