Talks
Spring 2021

Existentially Polytime Theorems

Thursday, Feb. 11, 2021 8:30 am9:30 am

Add to Calendar

Speaker: 

Jack Edmonds (University of Waterloo)

Location: 

Zoom

An EP theorem means an NP predicate which is always true. Most of most loved discrete theorems are EP. Usually, but not always, an EP theorem can be proved by a polynomial time algorithm which finds an instance of what the theorem says exists. A few examples are described.

AttachmentSize
PDF icon existentiallypolytimetheorems7.pdf1.04 MB