Preview

Информатика

Расширенный поиск

Логическая характеризация класса сложности задач, разрешимых вероятностными алгоритмами за полиномиальное время

Полный текст:

Аннотация

Рассмотрена проблема описания класса вычислительной сложности 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.)

Просмотров: 88


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)