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

Аннотация

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