Résultats intéressants dans TCS facilement explicables aux programmeurs sans formation technique

Supposons que vous rencontriez des programmeurs qui ont suivi des cours de programmation professionnelle (/ auto-réflexion) mais n'ont pas étudié les mathématiques de niveau universitaire.

Afin de leur montrer la beauté de TCS, j'aimerais rassembler de bons résultats / questions ouvertes provenant de TCS qui peuvent facilement être expliquées.

Un bon candidat à cet effet (IMHO) montrera que le problème de l'arrêt n'est pas décidable. Un autre montrera une limite inférieure sur le temps d'exécution du tri basé sur la comparaison (bien que cela le pousse un peu à partir de ce que je m'attends à ce qu'ils comprennent).

Je peux également utiliser les idées de Explain P = NP problem to 10 year old , en supposant que certains d'entre eux ne le connaissent pas.

Donc, les questions doivent être:

(0. Magnifique)

1. Explicable avec (au plus) les mathématiques du secondaire.
2. (de préférence) pas assez trivial pour être montré dans des cours de programmation professionnelle (pour C ++ / Java / Web / etc.).

En plus du problème d'arrêt, je suggère de discuter:

Théorème de Rice. Une partie de l'explication sur Wikipédia est un peu jargon, mais ce n'est généralement pas un théorème difficile ou une preuve à comprendre autre que cela; il est très pertinent pour les concepts du monde réel comme les logiciels antivirus. La preuve est à peu près aussi impliquée que la preuve du problème d'arrêt (et dépend en fait de l'indécidabilité du problème d'arrêt). Fondamentalement, comprenez simplement qu'une «fonction calculable» est une machine de Turing ou un programme informatique.

Je pense que - indépendamment de la question P vs NP - le théorème de Cook-Levin (et la notion connexe de complétude NP) est un autre très bon candidat; si vous avez un solveur (efficace) pour SAT, vous avez un solveur (efficace) pour tout problème dans NP .... et vous pouvez vous retrouver avec quelque chose d'étonnant au moins pour moi:

• $a x_1^2 + b x_2 + c = 0$
• résoudre un Sudoku;
• trouver un chemin hamiltonien dans un graphique;
• résoudre une instance de somme de sous-ensemble;
• et bien d'autres problèmes (réels) ...

sont en quelque sorte des "problèmes équivalents"; donc si votre patron vous demande de créer un programme pour emballer des boîtes dans un conteneur ... vous pouvez lui donner un solveur de démineur ... :-)

Un exemple amusant et divertissant est l'indécidabilité du problème de carrelage des carreaux Wang. Le résultat découle directement de l'indécidabilité du problème de l'arrêt par une simple simulation de machines de Turing utilisant des carreaux Wang. Fait intéressant, l'indécidabilité du problème de carrelage pour les carreaux Wang a conduit au beau résultat qu'il existe des ensembles de carreaux qui ne carrelent l'avion que de manière apériodique.

Wang a supposé que chaque jeu de tuiles qui tuile l'avion doit avoir un carrelage périodique. Par conséquent, la conjecture impliquait que le problème de carrelage est décidable. Plus tard, Burger a prouvé l'indécidabilité du problème de carrelage qui impliquait l'existence d'ensembles de carreaux qui ne carrelent l'avion que de façon apériodique.

$NP$$NP$

favoris collectés d'ici et d'ailleurs

• cryptographie à clé publique / algorithme RSA , fonctions de trappe , argument de comptage Shannons montrant que la plupart des fonctions de circuit sont difficiles ; re ce mystère:

  13.2 La plupart des fonctions sont difficiles, mais nous n'avons pas de mauvais exemples
  À la honte éternelle des informaticiens théoriques du monde entier, il n'y a pas d'exemple explicite connu d'une famille de fonctions [dures] ...

• Test AKS Primality en P , percée TCS relativement récente facilement communiquée

• P vs NP . une façon élémentaire de relier les fonctions NP est par le biais de jeux comme le cuirassé ou le soduku, tous deux avec des généralisations complètes NP. voir aussi par exemple le livre Fortnows . voir aussi les jeux vidéo comme NP complet

• indécidabilité du problème de correspondance postale

• Transformation du circuit de tséitine et SAT (réductions et exhaustivité du NP)

• (ancien) algorithme euclidien et connexion d'analyse du pire des cas à la séquence de Fibonacci

• Correspondance Curry-Howard entre épreuves et programmes . n'ont pas vu de référence élémentaire à ce sujet mais au fond l'idée est assez simple & communicable

• Thm en quatre couleurs via la vérification automatique du thm , une percée pour TCS