摘要：The preferred way to prove a parity theorem is an algorithm, which, for any given “desired object” X, finds a unique brother X’ (such that X’’=X, the brother of the brother of X is X). We survey several examples where the algorithms are beautiful, but can be shown to sometimes require an exponential number of steps, and we do not know whether there exist polynomial time algorithms. Examples include “Sperner”, “Lemke-Howson”, and “Hamilton paths in graphs”. 

报告人简介：Prof. Jack Edmondsis regarded as one of the most important contributors to the field of combinatorial optimization. He was the recipient of the 1985 John von Neumann Theory Prize.