The lecture:
POLYMATROIDS (Watch the recording of the lecture)
The talk will sketch an introduction to P, NP, coNP, LP duality, matroids, and some other foundations of combinatorial optimization theory.
A predicate, p(x), is a statement with variable input x. It is said to be in NP when, for any x such that p(x) is true, there is, relative to the bitsize of x, an easy proof that p(x) is true. It is said to be in coNP when ¬ p(x) is in NP. It is said to be in P when there is an easy (i.e., polynomially bounded time) algorithm for deciding whether or not p(x) is true. Of course P implies NP and coNP.
Fifty years ago I speculated the converse.
Polymatroids are a linear programming construction of abstract matroids. We use them to describe large classes of concrete predicates (i.e., "problems") which turn out to be in NP, in coNP, and indeed in P.
Failures in trying to place the NP "traveling salesman predicate" in coNP, and successes in placing some closely related polymatroidal predicates in both NP and coNP and then in P, prompted me to conjecture that
(1) the NP traveling salesman predicate is not in P, and
(2) all predicates in both NP and coNP are in P.
The conjectures have become popular, and are both used as practical axioms. I might as well conjecture that the conjectures have no proofs.
Monday, May 23 2011, 11:30
Download the poster
The course:
POLYMATROIDS ETCETERA: ALGORITHMS AND PRETTY THEOREMS
A variety of combinatorial existence theorems will be proved by algorithms which tell how to find an instance of what is asserted to exist. Another main purpose will be to introduce polyhedral combinatorics, which uses systems of linear equations to obtain algorithms and theorems. Emphasis will be on matroids and polymatro ids with a variety of applications, especially to tree systems and branching systems in networks.
TuesdayFriday, May 2427 2011, 10:30
Download the poster
If you like to receive reminders or notification of possible schedule changes, please drop your email address into the box below
"Pionereed by the work of Jack Edmonds, polyhedral combinatorics has proved to be a most powerful, coherent and unifying tool throughout combinatorial optimization. ..." "Edmonds conjectured that there is no polynomialtime algorithm for the traveling salesman problem. In language that was developed later, this is equivalent to NP¬=P."
from the book 'Combinatorial Optimization', by Lex Schrijver
"The classes of problems which are respectively known and not known to have good algorithms are of great theoretical interest. [...] I conjecture that there is no good algorithm for the traveling salesman problem. My reasons are the same as for any mathematical conjecture: (1) It is a legitimate mathematical possibility, and (2) I do not know." – Jack Edmonds, 1966
from the book 'Computational Complexity', by Christos Papadimitriou
"Jack Edmonds has been one of the creators of the field of combinatorial optimization and polyhedral combinatorics. His 1965 paper 'Paths, Trees and Flowers' was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms."
from the citation of the John Von Neumann Theory Prize, 1985
