Teoremas naturais comprovados apenas "com alta probabilidade"?

Existem muitas situações em que uma "prova" aleatória é muito mais fácil do que uma prova determinística, o exemplo canônico é o teste de identidade polinomial.

Pergunta : Existem "teoremas" matemáticos naturais em que uma prova aleatória é conhecida, mas uma prova determinística não?

Por uma "prova aleatória" de uma afirmação quero dizer que $P$

Existe um algoritmo aleatório que recebe uma entrada e se for falso produz uma prova determinística de com probabilidade pelo menos . $n > 0$ $P$ $\neg P$ $1-2^{-n}$
Alguém executou o algoritmo para, digamos, , e não refutou o teorema. $n = 100$

É fácil gerar declarações não naturais que se encaixam: basta escolher uma grande instância de qualquer problema em que apenas um algoritmo aleatório eficiente seja conhecido. No entanto, embora existam muitos teoremas matemáticos com "muitas evidências numéricas", como a hipótese de Riemann, não conheço nenhum deles com rigorosa evidência aleatória da forma acima.

lo.logic randomness randomized-algorithms proofs Geoffrey Irving
fonte

@ Kaveh: Obrigado pelas correções da categoria. Eu não tinha certeza do que colocá-lo.

Geoffrey Irving

outra direção, estudando a literatura de "des randomização" (procurando também uma boa pesquisa). O teorema de Reingold, relativamente recente (premiado) , também não foi um caso disso (novamente antes da prova)?

vzn

Bem nenhum problema com uma prova determinista descansando no ERH (como Primes costumava ser) teria esta propriedade

Suresh Venkat

Lamento dizer, mas não acho que sua pergunta faça sentido, pois não pode haver nenhuma dessas afirmações, naturais ou não. Você escreve que N é um primo costumava ser um bom exemplo, mas (é claro) sempre houve uma prova determinística para a primalidade, apenas um pouco mais. Também não consigo imaginar como você definiria a probabilidade de sucesso de um algoritmo que deveria refutar uma instrução de correção. Talvez você queira pedir uma prova eficiente para uma classe de problemas (ou seja, a entrada seria P e n e a declaração P (n)), mas então chegamos à teoria da complexidade e à definição de BPP.

Domotorp # 6/14

domotorp: É verdade que (supondo que o algoritmo use um número limitado de bits aleatórios) qualquer prova aleatória pode ser derandomizada com algum custo de desempenho. No entanto, estou perguntando exemplos em que o custo de desempenho é alto o suficiente para que a prova determinística não tenha sido executada até o momento, enquanto a prova aleatória o fez. Eu acredito que as definições fazem sentido nesse contexto.

Geoffrey Irving

Respostas:

$\DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj}$ Este não é um exemplo do que você está pedindo, mas sugere como esse exemplo pode acontecer. Algumas identidades combinatórias podem ser codificadas como identidades sobre polinômios de grau delimitado . Se os polinômios são univariados, para provar a identidade, basta verificar em pontos. No entanto, se os polinômios são multivariados e o grau é pelo menos moderadamente grande, o lema de Scwartz-Zippel pode ser a única maneira prática de verificar a identidade. $d$ $d+1$

Para um exemplo de caso univariado, consulte este artigo de Zeilberger, resolvendo uma questão de Knuth. Ele prova uma declaração sobre estatísticas de permutações. Para uma permutação , seja o número de inversões de , e deixar a maior índice de $\pi \in S_n$ $\inv(\pi)$ $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ $\pi$ $\maj(\pi)$ é a soma de todos os números inteiros no conjunto . Zeilberger prova que, para todos os , a covariância das duas estatísticas é $\pi$ $\{i: \pi(i+1) < \pi(i)\}$ $n$

E [(inv (π) - E [inv (π)]) \cdot (maj (π) - E [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},$ que todas as expectativas ultrapassam um uniformemente aleatório em . A prova de Zeilberger é apenas uma verificação por computador de e uma observação de que a afirmação é equivalente a uma identidade entre polinômios em de grau no máximo .

π

$\pi$

S_{n}

$S_n$

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

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

n

$n$

4

$4$

Sasho Nikolov
fonte

Obrigado, esse é um artigo adorável. Eu gosto bastante da moral.

Geoffrey Irving