Вероятностная проверка доказательств в исчислениях

В статье определяются системы вероятностно проверяемых доказательств специального вида, а именно, определяются исчисления с вероятностно проверяемыми доказательствами. Доказательство в таком исчислении можно проверить с достаточной достоверностью, не читая всё доказательство, а рассмотрев только один случайно выбранный путь в дереве доказательства – надо проверить все применения правил вывода вдоль этого пути. Время работы этой проверяющей процедуры предполагается полиномиальным от длины рассматриваемой теоремы. Показано, что дедуктивная мощность таких исчислений характеризуется следующим образом: (1) для любого исчисления с вероятностно проверяемыми доказательствами множество его теорем принадлежит PSPACE; (2) существует исчисление с вероятностно проверяемыми доказательствами, у которого множество теорем является PSPACE-трудным. Библ. – 14 назв.