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

13

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.).
RB
fuente
¿No es esto completamente basado en la opinión?
David Richerby
66
Creo que es una buena pregunta. Preguntas fructíferas similares sobre mathoverflow: mathoverflow.net/questions/47214/… . mathoverflow.net/questions/56547/applications-of-mathematics .
usul
1
también algo similar a la "descripción de la mesa de la cena de TCS" . en mi humilde opinión, mi favorito es la existencia de funciones duros probados por Shannon, pero las pruebas casi no constructivas de las funciones particulares duros después de más de medio siglo ....
VZN
1
Siempre es divertido mencionar a los programadores la existencia de quines.
Denis
2
tal vez debería ser wiki de la comunidad?
Suresh Venkat

Respuestas:

9

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.

Philip White
fuente
44
No creo que la dureza del factoring implique seguridad RSA.
Sasho Nikolov
1
Esa fue una brecha significativa en mi conocimiento de la criptografía. Gracias por señalar eso; Edité mi respuesta.
Philip White
1
Si está interesado, puede mirar esto: crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf . Sin embargo, su ejemplo fue agradable, incluso si los detalles eran incorrectos. Para Diffie-Hellman, la equivalencia al registro discreto es conocida para muchos grupos cíclicos, posiblemente los que se usan en aplicaciones prácticas: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3339 . Además, Diffie-Hellman es realmente más fácil de explicar que RSA, IMO
Sasho Nikolov
5

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í:

  • unX12+siX2+C=0 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 ... :-)

Marzio De Biasi
fuente
4

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 nortePAG-completo que se puede utilizar como un problema maestro para nortePAG-completos resultados.

Mohammad Al-Turkistany
fuente
3

favoritos recopilados aquí y en otros lugares

vzn
fuente
2
También otro algoritmo muy importante con algunos ángulos profundos de TCS: Pagerank
vzn