17234

Video URL

https://simons.berkeley.edu/talks/existentially-polytime-theorems

Existentially Polytime Theorems

(2021). Existentially Polytime Theorems. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/existentially-polytime-theorems

Existentially Polytime Theorems. The Simons Institute for the Theory of Computing, Feb. 11, 2021, https://simons.berkeley.edu/talks/existentially-polytime-theorems 

          @misc{ scivideos_17234,
            doi = {},
            url = {https://simons.berkeley.edu/talks/existentially-polytime-theorems},
            author = {},
            keywords = {},
            language = {en},
            title = {Existentially Polytime Theorems},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {feb},
            note = {17234 see, \url{https://scivideos.org/Simons-Institute/17234}}
          }
Jack Edmonds (University of Waterloo)
Talk number17234
Source RepositorySimons Institute
Subject

Abstract

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.