Resultados interesantes en TCS que son fácilmente explicables para programadores sin antecedentes técnicos

Suponga que se está reuniendo con programadores que han tomado algunos cursos de programación profesional (/ pensamiento propio) pero no estudiaron matemáticas a nivel universitario.

Para mostrarles la belleza de TCS, me gustaría reunir algunos buenos resultados / preguntas abiertas provenientes de TCS que puedan explicarse fácilmente.

Un buen candidato para este propósito (en mi humilde opinión) demostrará que el problema de detención no es decidible. Otro mostrará un límite inferior en el tiempo de ejecución de la clasificación basada en la comparación (aunque eso es un poco empujarlo de lo que espero que entiendan).

También puedo usar las ideas de Explain P = NP problem a 10 años , suponiendo que algunas de ellas no estén familiarizadas con él.

Entonces, las preguntas tienen que ser:

(0. Hermoso)

1. Explicable con (como máximo) matemáticas de secundaria.
2. (preferiblemente) no lo suficientemente trivial como para mostrarse en cursos de programación profesional (para C ++ / Java / Web / etc.).

Además del problema de detención, sugiero discutir:

El teorema del arroz. Algunas de las explicaciones en Wikipedia son un poco pesadas en jerga, pero generalmente no es un teorema ni una prueba difícil de entender aparte de eso; Tiene mucha relevancia para conceptos del mundo real como el software antivirus. La prueba es tan complicada como la prueba del problema de detención (y en realidad depende de la indecidibilidad del problema de detención). Básicamente, solo comprenda que una "función computable" es una máquina de Turing o un programa de computadora.

Creo que, independientemente de la pregunta P vs NP , el teorema de Cook-Levin (y la noción relacionada de completitud NP) es otro muy buen candidato; si tiene un solucionador (eficiente) para SAT, entonces tiene un solucionador (eficiente) para cualquier problema en NP ... y puede terminar con algo sorprendente al menos para mí:

• $a x_1^2 + b x_2 + c = 0$
• resolviendo un Sudoku;
• encontrar un camino hamiltoniano en un gráfico;
• resolver una instancia de suma de subconjuntos;
• y muchos otros problemas (de la vida real) ...

son en cierto sentido "problemas equivalentes"; así que si tu jefe te pide que crees un programa para empacar cajas en un contenedor ... puedes darle un solucionador de Buscaminas ... :-)

Un ejemplo divertido y entretenido es la indecidibilidad del problema de mosaico de los mosaicos Wang. El resultado se deriva directamente de la indecidibilidad del problema de detención mediante una simple simulación de máquinas de Turing que utilizan fichas de Wang. Curiosamente, la indecidibilidad del problema de mosaico para los mosaicos de Wang condujo al hermoso resultado de que hay conjuntos de mosaicos que mosaicos el plano solo aperiodicaly.

Wang conjeturó que cada conjunto de fichas que el plano debe tener mosaicos periódicos. Por lo tanto, la conjetura implicaba que el problema de mosaico es decidible. Más tarde, Burger demostró la indecidibilidad del problema de mosaico que implicaba la existencia de conjuntos de mosaicos que solo mosaicos el plano aperiodicaly.

La versión limitada del problema de mosaico es $NP$-completo que se puede utilizar como un problema maestro para $NP$-completos resultados.

favoritos recopilados aquí y en otros lugares

• algoritmo de criptografía de clave pública / RSA , funciones de trampillas , argumento de conteo de Shannons que muestra que la mayoría de las funciones de circuito son difíciles ; re este misterio:

  13.2 La mayoría de las funciones son difíciles, pero no tenemos ningún mal ejemplo
  Para la eterna vergüenza de los científicos teóricos de la informática en todas partes, no se conoce ningún ejemplo explícito de una familia de funciones [duras] ...

• Pruebas de AKS Primality en P , avance relativamente reciente de TCS fácilmente comunicado

• P vs NP . Una forma elemental de relacionar las funciones de NP es a través de juegos, por ejemplo, acorazado o soduku, ambos con generalizaciones completas de NP. Véase también, por ejemplo, el libro de Fortnows . ver también videojuegos como NP completo

• indecidibilidad del problema de correspondencia posterior

• Transformación de circuito de tseitina y SAT (reducciones de re y completitud de NP)

• (antiguo) algoritmo euclidiano y conexión del análisis del peor caso a la secuencia de Fibonacci

• Correspondencia de Curry-Howard entre pruebas y programas . no he visto una referencia elemental sobre esto, pero en el fondo la idea es bastante simple y comunicable

• Cuatro colores a través de pruebas automáticas , un avance para TCS