Природные теоремы доказаны только «с высокой вероятностью»?

Существует множество ситуаций, когда рандомизированное «доказательство» намного проще, чем детерминированное доказательство, каноническим примером является проверка полиномиальной идентичности.

Вопрос : Существуют ли естественные математические «теоремы», в которых рандомизированное доказательство известно, а детерминированное доказательство - нет?

Под «рандомизированным доказательством» утверждения $P$ я имею в виду, что

Существует рандомизированное алгоритм , который принимает входной сигнал $n > 0$ , и если $P$ является ложным производит детерминированное доказательство $\neg P$ с вероятностью по крайней мере $1-2^{-n}$ .
Кто-то запустил алгоритм, скажем, для $n = 100$ , и не опроверг теорему.

Легко генерировать неестественные утверждения, которые подходят: просто выберите большой экземпляр любой проблемы, для которой известен только эффективный рандомизированный алгоритм. Однако, хотя существует много математических теорем с «большим количеством числовых доказательств», таких как гипотеза Римана, я не знаю ни одного с точным рандомизированным доказательством вышеуказанной формы.

lo.logic randomness randomized-algorithms proofs Джеффри Ирвинг
источник

@Kaveh: Спасибо за исправления категории. Я не был уверен, что положить его под.

Джеффри Ирвинг

другое направление, изучение литературы по "дерандомизации" (также ищем хороший обзор). Разве относительно недавняя (отмеченная наградами) теорема Рейнгольда также не является случаем этого (опять же до доказательства)?

vzn

Что ж, любая проблема с детерминированным доказательством, опирающимся на ERH (как раньше были Primes), имела бы это свойство

Суреш Венкат

Мне жаль говорить, но я не думаю, что ваш вопрос имеет смысл, поскольку не может быть таких заявлений, естественных или нет. Вы пишете, что N - простое число, которое раньше было хорошим примером, но (конечно) всегда было и детерминированное доказательство простоты, только немного дольше. Я также не могу представить, как вы определяете вероятность успеха алгоритма, который должен опровергнуть одно утверждение исправления. Может быть, вы хотите запросить эффективное доказательство для класса задач (т. Е. Входными данными будут P и n и утверждение P (n)), но затем мы подходим к теории сложности и определению BPP.

Domotorp

domotorp: Это правда, что (если алгоритм использует ограниченное количество случайных битов), любое такое рандомизированное доказательство может быть дерандомизировано с некоторыми затратами на производительность. Однако я спрашиваю о примерах, когда стоимость производительности достаточно высока, чтобы детерминированное доказательство не было выполнено до настоящего времени, в то время как рандомизированное доказательство имело место. Я считаю, что определения имеют смысл в этом контексте.

Джеффри Ирвинг

$\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj}$ Это не пример того, что вы просите, но он предлагает, как такой пример может возникнуть. Некоторые комбинаторные тождества могут быть закодированы как тождества о многочленах ограниченной степени . Если многочлены одномерные, для доказательства тождества достаточно проверить его по баллам. Однако, если многочлены являются многомерными, а степень по крайней мере умеренно большой, лемма Скварца-Циппеля может быть единственным практическим способом проверки идентичности. $d$ $d+1$

Для примера одномерного случая, проверьте эту статью Zeilberger, решая вопрос Кнута. Он доказывает утверждение о статистике перестановок. Для перестановки пусть будет числом - сумма всех целых чисел в множестве $\pi \in S_n$ $\inv(\pi)$ инверсий , и пусть основной индекс из $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ $\pi$ $\maj(\pi)$ $\pi$ . Цейлбергер доказывает, что для всех ковариация двух статистик $\{i: \pi(i+1) < \pi(i)\}$ $n$

где все ожидания более равномерно случайныйв. Доказательство Цейлбергера - это просто компьютерная проверка для

Е [(фактура (π) - Е [фактура (π)]) \cdot (Maj (π) - Е [Maj (π)])] знак равно \frac{1}{4} (\binom{N}{2}),

$\mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2},$

π

$\pi$

S_{n}

$S_n$

и наблюдение, что утверждение эквивалентно тождеству между полиномами по

степени не более

n \in {1, 2, 3, 4, 5}

$n \in \{1, 2, 3, 4, 5\}$

n

$n$

4

$4$

Сашо Николов
источник

Спасибо, это прекрасная статья. Мне очень нравится мораль.

Джеффри Ирвинг

Природные теоремы доказаны только «с высокой вероятностью»?

Ответы: