Аннотация:
Первопорядковая логика вероятности с распределением на носителе — известный формальный язык для рассуждения о вероятностях в теоретической информатике, предложенный Дж. Хальперном. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам.
Сложность вышеупомянутой логики была изучена М. Абади и Дж. Хальперном (1994). Основной интерес здесь представляют нижние сложностные оценки. Для их получения в статье М. Абади и Дж. Хальперна существенно использовались сложение и умножение между вероятностями. В настоящем докладе будет показано, как получить те же самые сложностные оценки для малых «качественных» (англ. qualitative) фрагментов, в которых нет ни сложения, ни умножения. В частности, в односортном случае будет достаточно равенств между вероятностями от бескванторных первопорядковых формул.
Обратная связь: