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

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.).

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.

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:

• $a x_1^2 + b x_2 + c = 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 ... :-)

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.

$NP$$NP$

favoritos coletados aqui e em outros lugares

• algoritmo de criptografia de chave pública / RSA , funções de alçapão , argumento de contagem de Shannons mostrando que a maioria das funções de circuito é difícil ; re este mistério:

  13.2 A maioria das funções é difícil, mas não temos exemplos ruins
  Para a vergonha eterna dos cientistas teóricos da computação em todos os lugares, não há um exemplo explícito conhecido de uma família de funções [difíceis] ...

• Teste de AKS Primality em P , avanço relativamente recente do TCS facilmente comunicado

• P vs NP . Uma maneira elementar de relacionar funções de NP é através de jogos, por exemplo, encouraçado ou soduku, ambos com generalizações completas de NP. veja também, por exemplo, o livro Fortnows . veja também videogames como NP completo

• indecidibilidade do problema de pós-correspondência

• Transformação de circuitos de tseitina e SAT (re-reduções e completude de NP)

• Algoritmo euclidiano (antigo) e conexão de análise de pior caso à sequência de Fibonacci

• Correspondência de Curry-Howard entre provas e programas . não vi uma referência elementar sobre isso, mas no fundo a idéia é bastante simples e comunicável

• Thm de quatro cores através da prova automática de thm , uma inovação para o TCS