Théorie de calcul : Complexité monotone et limites inférieures de XOR-SAT

Cette séance de cours s'inscrit dans la théorie du calcul, en mettant l'accent sur la complexité monotone et les limites inférieures de XOR-SAT. Il couvre le concept de circuits monotone, l'absence de portes de négation et les implications des circuits monotone dans le problème P vs NP. L'instructeur présente un nouveau théorème lié inférieur lié à XOR-SAT, mettant en évidence la complexité des circuits monotones. De plus, des exemples de calculs monotones sont fournis pour illustrer les concepts discutés. La séance de cours se termine par un aperçu de divers sujets dans le domaine, tels que l'optimisation, la théorie de l'apprentissage et la complexité des preuves.