Existentially Polytime Theorems

APA

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

MLA

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

BibTex

          @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)
Source Repository Simons Institute

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.