Problème de suppression : P vs NP

Cette séance de cours explore le problème d'arrêt, démontrant l'indécidabilité de déterminer si un programme s'arrête lorsqu'il est exécuté avec lui-même comme entrée. Il s'inscrit dans la théorie de la complexité, en discutant de la classe P pour les problèmes solubles dans le temps polynôme, contrastant avec la classe NP pour les problèmes polynômes non déterministes. La séance de cours porte également sur les algorithmes pratiques, la mesure de la complexité et des exemples de problèmes en P et en NP. Il se termine par une discussion sur les problèmes de Traveling Salesman et Knapsack, illustrant les défis de trouver des solutions optimales au sein de la complexité du NP.