Resultados interessantes no TCS, que são facilmente explicáveis ​​para programadores sem formação técnica

13

Suponha que você esteja se encontrando com programadores que fizeram alguns cursos profissionais de programação (/ pensamento próprio), mas não estudaram matemática em nível universitário.

Para mostrar a eles a beleza do TCS, gostaria de reunir alguns bons resultados / perguntas abertas provenientes do TCS, que podem ser facilmente explicados.

Um bom candidato para esse fim (IMHO) mostrará que o problema da parada não é decidível. Outro mostrará um limite inferior no tempo de execução da classificação baseada em comparação (embora isso seja um pouco diferente do que eu espero que eles entendam).

Também posso usar as idéias do problema Explain P = NP para 10 anos , assumindo que algumas delas não estão familiarizadas com isso.

Então, as perguntas devem ser:

(0. Lindo)

  1. Explicável com (no máximo) matemática do ensino médio.
  2. (de preferência) não é trivial o suficiente para ser mostrado em cursos de programação profissional (para C ++ / Java / Web / etc.).
RB
fonte
Isso não é totalmente baseado em opiniões?
David Richerby
6
Eu acho que é uma boa pergunta. Perguntas semelhantes e proveitosas sobre mathoverflow: mathoverflow.net/questions/47214/… . mathoverflow.net/questions/56547/applications-of-mathematics .
usul
1
também um pouco semelhante à "descrição da mesa de jantar do TCS" . imho o meu favorito é a existência de funções difíceis comprovadas por Shannon, mas provas quase nenhuma construtivas de quaisquer funções rígidos particulares depois de mais de 1/2 do século ....
vzn
1
A existência de quines é sempre divertida de mencionar aos programadores.
Denis
2
talvez deva ser wiki da comunidade?
Suresh Venkat

Respostas:

9

Além do problema de parada, sugiro discutir:

Teorema de Rice. Algumas das explicações na Wikipedia são um pouco exageradas, mas geralmente não é um teorema ou uma prova difícil de entender além disso; tem muita relevância para conceitos do mundo real, como software antivírus. A prova é tão envolvida quanto a prova do problema de parada (e realmente depende da indecidibilidade do problema de parada). Basicamente, apenas entenda que uma "função computável" é uma máquina de Turing ou programa de computador.

Philip White
fonte
4
Não acho que a dureza de fatorar implique segurança RSA.
Sasho Nikolov 08/02
1
Essa foi uma lacuna significativa no meu conhecimento de criptografia. Obrigado por apontar isso; Eu editei minha resposta.
Philip White
1
Se você estiver interessado, você pode olhar para isto: crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf . No entanto, seu exemplo foi bom, mesmo que os detalhes estivessem incorretos. Para Diffie-Hellman, a equivalência ao log discreto é conhecida por muitos grupos cíclicos, incluindo indiscutivelmente os utilizados em aplicações práticas: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3339 . Além disso, Diffie-Hellman é realmente mais fácil de explicar do que RSA, IMO
Sasho Nikolov
5

Penso que - independentemente da questão P vs NP - o teorema de Cook-Levin (e a noção relacionada de completude de NP) é outro candidato muito bom; se você tem um solucionador (eficiente) para o SAT, você tem um solucionador (eficiente) para qualquer problema no NP .... e pode acabar com algo surpreendente pelo menos para mim:

  • umax12+bx2+c=0 0
  • resolvendo um Sudoku;
  • encontrar um caminho hamiltoniano em um gráfico;
  • resolver uma instância de soma de subconjuntos;
  • e muitos outros problemas (da vida real) ...

são, em certo sentido, "problemas equivalentes"; portanto, se seu chefe solicitar que você crie um programa para empacotar caixas em um contêiner ... você pode fornecer a ele um solucionador de caça-minas ... :-)

Marzio De Biasi
fonte
4

Um exemplo divertido e divertido é a indecidibilidade do problema de ladrilhos dos azulejos Wang. O resultado segue diretamente da indecidibilidade do problema de Halting por uma simulação simples de máquinas de Turing usando ladrilhos Wang. Curiosamente, a indecidibilidade do problema de ladrilhos para os ladrilhos Wang levou ao belo resultado de que existem conjuntos de ladrilhos que ladrilham o avião apenas periodicamente.

Wang conjeturou que todo conjunto de ladrilhos que ladrilhavam o avião deveria ter ladrilhos periódicos. Portanto, a conjectura implicava que o problema do ladrilho é decidível. Mais tarde, Burger provou a indecidibilidade do problema de ladrilhos, o que implicava a existência de conjuntos de ladrilhos que ladrilhavam o avião apenas periodicamente.

NPNP

Mohammad Al-Turkistany
fonte
3

favoritos coletados aqui e em outros lugares

vzn
fonte
2
Também outro algoritmo muito importante com alguns TCS profundas ângulos: Pagerank
vzn