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 bit-size 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
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.
Tuesday-Friday, May 24-27 2011, 10:30
Download the poster
If you like to receive reminders or notification of possible schedule changes, please drop your e-mail address into the box below
"Pionereed by the work of Jack Edmonds, polyhedral combinatorics
from the book 'Combinatorial Optimization', by Lex Schrijver
has proved to be a most powerful, coherent and unifying tool
throughout combinatorial optimization. ..."
"Edmonds conjectured that there is no polynomial-time algorithm for the
traveling salesman problem. In language that was developed later, this is
equivalent to NP¬=P."
"The classes of problems which are respectively known and not
from the book 'Computational Complexity', by Christos Papadimitriou
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
"Jack Edmonds has been one of the creators of the field
from the citation of the John Von Neumann Theory Prize, 1985
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."