Доказательства в арифметике, использующие случайные числа

В статье предлагается система доказательств с использованием случайных чисел для арифметики. Доказательство формулы $S$ в этой системе определяется как вывод $S$ из аксиом арифметики посредством правил вывода арифметики и еще одного правила, которое называется правилом случайной подстановки, и в котором используются случайные числа. Такие доказательства можно рассматривать также как интерактивные доказательства специального вида и, более точно, как частный случай доказательств вида Артур–Мерлин ([3], [5]). Основной результат статьи показывает, что доказательство в арифметике с правилом случайной подстановки может быть существенно короче чем обычное доказательство той же формулы в арифметике. А именно, построено множество арифметических формул $T$ такое, что (1) все формулы из $T$ доказуемы в арифметике, но, если только $\mathrm{PSPACE}\ne\mathrm{NP}$, не имеют доказательств полиномиальной длины; (2) формулы из $T$ имеют доказательства полиномиальной длины и с экспоненциально малой вероятностью ошибки в арифметике с правилом случайной подстановки (какие бы случайные числа ни появлялись в ходе доказательства). Библ. – 10 назв.