Resultados contra-intuitivos para estudantes de graduação

14

Estou procurando exemplos de resultados que vão contra a intuição das pessoas para uma conversa na audiência geral. Resultados que, se perguntados a não especialistas "o que sua intuição lhe diz?", Quase todos entendem errado. A declaração de resultados deve ser facilmente explicável aos alunos de graduação em cs / math. Estou procurando principalmente resultados em ciência da computação.

Quais são os resultados mais contra-intuitivos / inesperados (de interesse geral) em sua área?

Anônimo
fonte
1
O segundo link do Sasho é duplicado, não?
Huck Bennett
Semelhante, mas não o mesmo. Estou procurando resultados interessantes e contra-intuitivos para os estudantes de graduação em cs / matemática em geral, e não para os pesquisadores. Por exemplo, IP = PSPACE não seria uma boa resposta.
Anônimo
4
Para tamanhos de entrada suficientemente grandes, a primalidade sempre pode ser decidida em menos tempo do que a maneira mais rápida conhecida de ter uma chance não negligenciável de fatorar um módulo RSA.

Respostas:

25

Para uma audiência geral, você precisa se atentar às coisas que elas podem ver . Assim que você começar a teorizar, eles iniciarão seus telefones celulares.

Aqui estão algumas idéias que poderiam ser elaboradas para completar exemplos:

  1. Existe uma superfície que tem apenas um lado .
  2. Uma curva pode preencher um quadrado inteiro .
  3. Existem curvas de largura constante diferentes de um círculo.
  4. É possível colorir o plano com três cores, de forma que cada ponto de borda seja uma triagem .

Se você pode confiar em um pouco de conhecimento matemático, pode fazer mais:

  1. Existem tantos números ímpares quanto números naturais.
  2. Há uma função contínua e em nenhum lugar diferenciável .
  3. Existe uma função que é descontínua em todos os números racionais e diferenciável em todos os números irracionais.f:RR
  4. O "paradoxo" de Banach-Tarski .

Para programadores, você pode tentar:

  1. Os funcionais impossíveis : existe um programa que usa um predicado p : stream → bool, onde streamestá o tipo de dados de seqüências binárias infinitas e retorna truese e somente se p αé truepara todos os fluxos α(que são incontáveis ​​muitos), e falsecaso contrário.

  2. É possível jogar pôquer por telefone de maneira confiável, o que evita trapaças.

  3. Um grupo de pessoas pode calcular seu salário médio sem que ninguém descubra o salário de outra pessoa.

  4. Existe um programa que constrói uma árvore binária T com as seguintes propriedades:

    • a árvore é infinitaT
    • não há programa que rastreie um caminho infinito em T
Andrej Bauer
fonte
o paradoxo de Banach-Tarski (e paradoxos relacionados) tem a ver com noções (e manipulações) do infinito, algo que mesmo os matemáticos profissionais podem errar (ou discordar muito sobre isso) :)
Nikos M.
4
Concordou, mas é o tipo de teorema ouriço que desperta o interesse das pessoas. Isso dá a eles uma sacudida e os faz duvidar de suas próprias intuições sobre o infinito.
Andrej Bauer
17

Uma idéia é algo simples dos algoritmos de streaming . Provavelmente, o melhor candidato é o algoritmo majoritário. Digamos que você veja um fluxo de números , um após o outro, e saiba que um número ocorre mais da metade do tempo, mas não sabe qual. Como você pode encontrar o número majoritário se consegue lembrar apenas dois números por vez ? A resposta é o algoritmo Misra-Gries.s1,,sn

A cada etapa, você armazena um número do fluxo e um contador de frequência f . No início, você define x para o primeiro número do fluxo e inicializa a frequência f para 1. Então, sempre que você vê um novo número s i , verifica se x = s ixfxfsix=si . Se , aumente f para f + 1 , caso contrário, diminua f para f - 1 . Se f = 0 , defina x como s ix=siff+1ff1f=0 0xsEue volta para 1 . Após o último elemento do fluxo, se houver um elemento majoritário, ele será igual a x .f1x

Outra idéia é o jogo conhecido para ilustrar zero provas de conhecimento . Eu acho que é devido a Oded Goldreich e é semelhante à prova de zero conhecimento para isomorfismo de gráfico.

Para tornar a resposta independente, aqui está o jogo. Suponha que você queira convencer seu amigo daltônico de que pode distinguir o vermelho do verde. Seu amigo tem dois baralhos de cartas e ele sabe que uma pilha é verde e a outra é vermelha. Ele faz o seguinte sem você vê-lo: com probabilidade 1/2, ele compra uma carta de cada baralho, com probabilidade 1/4, ele compra duas cartas do baralho esquerdo e, com probabilidade 1/4, ele compra duas cartas do baralho direito . Então ele mostra as cartas e pergunta se elas são da mesma cor. Se você não é daltônico, é claro que pode responder sempre corretamente. Se você é daltônico, irá falhar com probabilidade 1/2. Portanto, agora, se o jogo for jogado 10 vezes, a probabilidade de você vencer sempre que for daltônica é extremamente baixa.

O problema é que, se seu amigo sabia que os dois baralhos são de duas cores diferentes, mas não sabia qual é o vermelho e o verde, ele ainda não saberá ao final disso! Então, em resumo:

  1. Há lugar para a aleatoriedade nas provas.
  2. Você pode convencer alguém que conhece alguma coisa sem fornecer a ela nenhuma informação.
Sasho Nikolov
fonte
3
Além de Misra-Gries, também acho que a amostragem de reservatório é simples, mas agradável.
Juho
1
@ Juho eu concordo. Uma pergunta de entrevista popular para inicializar :).
Sasho Nikolov 26/05
13

O volume de uma esfera unitária de dimensão cresce primeiro à medida que n cresce ( 2 , π , 4 π / 3nn ), mas começa a diminuir para n = 6 e, eventualmente, converge para 0 como n .2,π,4π/3,n=60n

Denis
fonte
1
E a razão para isso é a decisão arbitrária de considerar esferas de raio unitário, em oposição a outro parâmetro de comprimento. Em particular, os volumes de esferas de diâmetro 1 estão diminuindo desde o início.
Emil Jerabek suporta Monica
Há muitos fatos divertidos e contra-intuitivos relacionados à geometria em altas dimensões. Por exemplo, pegue o hipercubo da unidade e inscreva uma esfera tocando todos os lados. A que distância está um canto do hipercubo da esfera? (Resposta: diverge para à medida que a dimensão cresce. O raio da esfera é 0,5 , mas a distância do centro ao canto do cubo é 0,5 0.50.5n .)
usul 16/10
10

Um resultado contra-intuitivo da teoria da complexidade é o teorema do PCP:

Informalmente, afirma que para cada NP problema , existe uma máquina de Turing randomizado eficiente, que pode verificar a exactidão prova (provas de adesão em um ) usando o número de bits aleatórios logarítmica e lendo apenas um número constante de bits da prova. A constante pode ser reduzida para 3 bits. Portanto, o verificador aleatório precisa ler apenas três bits da prova proclamada.UMAUMA

Mohammad Al-Turkistany
fonte
Qual é a referência para "pode ​​ser reduzido para 3 bits"?
Ryan
2
Isso é conhecido como teorema do PCP de 3 bits (ou 3 consultas) de Håstad, e requer sacrificar a perfeição perfeita
Joe Bebel
1
Aqui você encontra mais informações e a referência ao artigo de Håstad: people.csail.mit.edu/madhu/papers/1998/glst.pdf
Mohammad Al-Turkistany
6
@JoeBebel Na verdade, existem verificadores de 3 bits com perfeição completa. O verificador de Hastad é "linear": ele pega três bits e pega seu XOR. Para esse verificador, você precisa sacrificar a perfeição. Aliás, existem provas de PCP que lêem apenas dois bits (novamente necessariamente sem perfeição completa). Por exemplo, veja minha resposta aqui cstheory.stackexchange.com/a/20549/4896
Sasho Nikolov
9

Uma coisa que se mostra contra-intuitiva para os graduandos de CS é o fato de poder selecionar as estatísticas de ordem de uma ordem não ordenada de n elementos em O ( n ) tempo. Todos os alunos pensam que devem primeiro necessariamente classificar a matriz (em O ( n l g n ) tempo).EunO(n)O(n eug n)

Massimo Cafaro
fonte
7

Com base na resposta / ângulo dos MdBs, um resultado clássico de algo contra - intuitivo no momento da descoberta no TCS em seus fundamentos é a existência da (des) decidibilidade em si. na virada do século XX , Hilbert, refletindo o pensamento de outros matemáticos importantes da época, pensava que a matemática poderia ser sistematizada (um pouco na forma do que agora reconhecemos como algorítmica ) e um pouco através do conceito de "finitismo" ( que tem paralelos aproximados com a idéia de um algoritmo como uma sequência finita de etapas). ele propôs famosos problemas abertos nesse sentido. sua intuição (e outras) se mostrou errada de uma maneira espetacular. a contraprova éTeorema de Godels e problema de Turings Halting . ambos eram conceitos / resultados extremamente abstratos e documentos / argumentos longos e altamente técnicos, apenas compreensíveis para os principais matemáticos da época, mas agora são refinados para estruturas conceituais mais simples e ensinados aos estudantes de graduação. estes não foram inicialmente vistos como dois aspectos / face do mesmo fenômeno, mas agora são.

também demorou quase um século para provar que equações diofantinas inteiras são indecidíveis, o décimo problema de Hilberts . isso é contra-intuitivo no sentido de que sempre se soube que a teoria dos números era extremamente difícil, mas o conceito de que alguns problemas específicos / identificáveis ​​na verdade podem ser "impossíveis de resolver" era quase chocante para alguns. a indecidibilidade continua sendo um desafio profundo em matemática / TCS, mesmo que tenhamos décadas de aumentos exponenciais em hardware devido à lei de Moores e, no entanto, supercomputadores maciços que, de certa forma, ainda são "impotentes contra ela". alguns aspectos da surpresa da indecidibilidade podem ser encontrados no livro Mathematics, Loss of Certainty, de Klein.

vzn
fonte
2
O artigo de Turing não era extremamente abstrato / técnico. Na verdade, é bastante direto e acessível.
Jeffε
1
Tudo bem, talvez para você agora, mas quantos alunos de graduação você sabe quem pode acompanhar todo o artigo? se você segui-lo como uma graduação? por que o conteúdo real completo não é coberto nas aulas de graduação? por que um livro inteiro foi escrito analisando esse único artigo? o que dizer de partes que antecipam conceitos que não foram descobertos até décadas depois , como correspondência com curry-howard , linguagens de programação de alto nível etc.?
Vzn 30/05
3
Ainda assim, "documentos / argumentos longos e altamente técnicos, apenas compreensíveis para os principais matemáticos da época", não são precisos no artigo de Turing, que é uma ordem de magnitude mais acessível que os documentos de Godel. Esta resposta está cheia de não-sequestradores. Não vejo o que o finitismo tem a ver com o programa de Hilbert (tenho certeza de que ele não seria um finitista). O que a lei de Moore tem a ver com indecidibilidade também é um enigma para mim. Você realmente esperaria que um hardware exponencialmente mais rápido resolvesse problemas indecidíveis ?
Sasho Nikolov
3
por que o conteúdo real completo não é coberto nas aulas de graduação? - Não há tempo suficiente.
Jeffε 30/05
1
Justo, eu não sabia sobre o finitismo de Hilbert. Eu só conhecia as noções modernas e muito mais rigorosas de finitismo. Seria melhor se você escrevesse uma boa resposta em vez de encaminhar as pessoas para conversar, mas de alguma forma duvido que você siga este conselho.
Sasho Nikolov
6

Parece óbvio, mas, por experiência pessoal, a idéia de que você pode estimar a mediana de uma coleção de itens usando um número constante de operações é um pouco chocante. E se isso parecer um pouco técnico demais, você sempre pode convertê-lo em uma declaração sobre pesquisas e eleições (você precisa de 1300 pessoas para obter uma amostra com 3% de erro, independentemente do tamanho da população).

Relacionado a isso, é claro, o paradoxo do aniversário .

Suresh Venkat
fonte
5

Talvez um bom exemplo (não diretamente relacionado à complexidade computacional) seja a universalidade de Turing de modelos computacionais simples.

Por exemplo, a regra 110 é universalmente eficiente (fracamente):

Dada uma matriz (infinita) de 0-1 (branco-preto) células adequadamente inicializadas e as regras de substituição simples:

insira a descrição da imagem aqui

nós temos um "computador de trabalho"! :-)

Para a definição de "fracamente" e "eficiente", e para outros exemplos de máquinas de Turing universais simples, veja: Turlough Neary, Damien Woods; A complexidade das pequenas máquinas universais de Turing: uma pesquisa .

Outro exemplo intrigante é a integridade de Turing da "linguagem de programação" do FRACTRAN :

  • (p1/q1,p2/q2,...,pn/qn)
  • nqEunnnpEuqEu
  • qEun

n

Você também pode usar outros modelos, como sistemas de etiquetas cíclicas, autômatos de formigas,
etc. A idéia não tão intuitiva é que a "computação" está escondida em quase todos os lugares ... Wolfram escreveu 1192 páginas cheias de figuras e texto para melhor expresse essa idéia em seu livro Um Novo Tipo de Ciência (sim ... sim ... apesar de algumas críticas, finalmente comprei uma cópia impressa dela :-)

Marzio De Biasi
fonte
3

Alguns bons candidatos de cabeça para baixo:

  • Todo NFA possui um DFA equivalente

  • ppEuEuNEu>0 0

  • Criptografia de chave pública

    • Chamando para uma função com argumentos criptografados e recebendo o resultado desejado sem revelar informações sobre suas entradas

    • Criptografia RSA

  • Códigos Reed-Salomão

  • Contabilidade

    • |N|=|Z|=|N×N|=|Q|

    • {0 0,1}R

    • |S|<|P(S)|

  • Em um nível mais filosófico, me surpreendeu que as máquinas de Turing definissem com precisão a computação

Bharadwaj Ramachandran
fonte