We are glad to have Jack Edmonds with us in Lisbon from the February 16 till March 3.

Jack will give a few lectures in the course Advanced Algorithms and the talk below on February 20, at 13:30 (FA3, Pavilhão de Informática III, Alameda).

Everyone is welcome.

Origins of NP and P.

Jack Edmonds. A talk in Lisbon, February 2019 (slides available).

Long Advertisement:

NP and P have origins in “the marriage theorem”:
A matchmaker has as clients the parents of some boys
and some girls where some boy-girl pairs love each other.
The matchmaker must find a marriage of all the girls to distinct boys they love
or else prove to the parents that it is not possible. The input to
this marriage problem is usually imagined as a bipartite graph G
with boy nodes, girl nodes, and edges between them representing love.
A possible legal marriage of some of the girls to some of the boys
is represented by a subset M of the edges of G, called a matching.
The matchmaker’s problem is to find a matching which hits all the girl nodes
Or else prove to the parents that there is none.

A predicate p(t) is a statement with a variable input t.
For example, p(t) might be the statement:
“There is a matching in bipartite graph, t, which hits all the girl nodes.”
This particular predicate p(t) is in complexity class NP because
whenever it is true there is an easy way relative to the size of t
to show the parents that it is true.
This predicate is also in coNP because the marriage theorem provides,
whenever t is such that p(t) is not true, an easy way to show the parents
that there is no matching in G which hits all the girl nodes.
(Of course we need a mathematical definition of “easy”.)

It turns out that this predicate p(t) is also in complexity class, P.
That is, relative to the size of t,
there is an easy algorithm to decide whether or not p(t) is true.

Thinking about this in 1960, it occurred to me that maybe
a general predicate p(t) is in P whenever it is in NP ∩ coNP.
It is still not known whether or not P = NP ∩ coNP in general
but it has turned out to be often true. I think this is the origin of NP.

The optimum assignment problem, in a yes-no form, is
given t = (a bipartite G, a numerical weight cj for each edge j, a matching M in G),
is p(t) true or false, where
p(t) is the statement “M is not the largest total weight matching in G” ?

Obviously this predicate p(t) is in NP because whenever p is true
we can show it easily by showing a larger weight matching.
Is this p in coNP? i.e. is “M is a maximum weight matching in G” in NP?
The 1931 Egervary Theorem says yes because it provides an easy
way to prove when an M is optimum.

Implicit in Egervary’s proof is an easy algorithm for deciding
whether or not the matching M is optimum, and so
this predicate p(t) is in complexity class P.
In 1954 Kuhn dubbed it “the Hungarian Method”.
Silvano Martello and friends have a fine book called
“Assignment Problems”.
http://www.or.deis.unibo.it/staff_pages/martello/cvitae.html

Egervary’s Theorem is the first known instance of
the linear programming duality theorem.
George Dantzig introduced the general field of linear programming,
and invented the simplex method for solving linear programs,
in the late 1940s.

A thrill of my life was in the mid 1960s showing to Dantzig’s l.p. class
that the simplex method can grow exponentially
even for shortest path problems, and so it does not put l.p. into P. In the
1980s Khachian showed that “the ellipsoid method” does put l.p. into P.
(The Hungarian method is not the simplex method or the ellipsoid method.)

Linear programming has become since the 1950s a foundation of
departments of operations research, management science,
or industrial engineering.

The matchings M in a graph G are represented by vectors x
with a coordinate for each edge j in the edge-set E of G.
“(Incidence) vector” x of M is x_j = 1 if j of E is in M, and x_j = 0 if j of E is not in M.
Thus an optimum matching is the vector x of a matching
which maximizes a given linear function, cx, over matching vectors, x.

The convex hull of any finite set Q of points (vectors) in the space
of vectors indexed by the edge-set E of graph G, is a polytope,
the bounded solution-set of a finite set L of linear inequalities.
Thus optimizing cx over members of Q is the same as
the linear program of optimizing cx subject to L.
Normally for an easily described finite set Q of points in R^E,
the number of inequalities needed in L is exponentially large relative to │E│.
Dantzig’s simplex algorithm would then be very exponential time.

An arrangement of the girls and boys around a banquet table
so that each is, on each side, next to someone loved,
is the same as a ‘Hamilton tour’ in the graph G. Suppose we want
a Hamilton tour C which optimizes the sum of love-weights on edges in C.
The Traveling Salesman Problem, in a yes-no form, is given
t = (a graph G, a love-weight c_j for each edge j, a Hamilton cycle H in G),
then where p(t) = [H is not the largest total love-weight Hamilton tour in G],
is p(t) true or false? This predicate is clearly in NP.

In 1971 Steve Cook, and independently Leonid Levin,
showed that there exist NP complete predicates (“problems”).
Dick Karp showed that many natural combinatorial problems,
including the Traveling Salesman Problem, are NP complete. And hence an easy
algorithm for any one of them implies an easy algorithm for any NP predicate.

Throughout the 1960s , though in looking for easy algorithms of course I found
some easy reductions between problems, I never dreamed that there exists NP
complete problems. It is a holy tragedy that so many NP complete problems
have even given NP a bad name, when NP itself is a wonderfully positive thing.

In 1954, Dantzig, with Ray Fulkerson and Selmer Johnson,
solved a particular 48-city traveling salesman problem
by using linear programming. Their linear inequality system L’,
satisfied by all the Hamilton tour vectors, is easy to describe,
though exponentially large. Unfortunately the solution-set of L’ has
some extreme points which are fractional rather than Hamilton tour vectors,
and so optimizing subject to L’ might not be by a Hamilton tour.
Their work motivated Ralph Gomory in 1958
to introduce cutting plane methods for integer linear programming.
There was no mention of ‘easy’, meaning polynomially bounded time.

Their work prompted me in 1961 to notice the simple result
that if there is an easy (i.e., NP) description of the set L
of inequalities describing the convex hull of finite point-set Q,
as well as an easy description of the members of Q,
then it does not matter that L is exponentially large in order to have that
the predicate p(t) = [point x of Q is optimum over Q] is in NP ∩ coNP.

And maybe that puts “optimize over Q” algorithmically into P.

It seemed plausible that if there is an easy description of Q
then there might be an easy description of a linear system, L,
describing the convex hull of Q. That is an important step
toward an easy general algorithm for optimizing over Q.

In particular I tried hard to find an NP description of a linear system L
whose solution-set is the convex hull of the vectors of Hamilton tours
in a complete graph, G. I was never able to, and so I conjectured that
NP is not equal to P, in particular that the TSP is not in P.

This conjecture is now usefully presumed. It is at the top of the Clay list
of unsolved math problems. Curiously it is the only problem in the list i
which is posed as a question rather than as a conjecture,
so it does not need to be called “Edmonds’ conjecture”.

During the 1960s, the decade before the discovery of NP completeness, as part of
the search for TSP in P, I did find some instances of easily described sets Q to have
NP descriptions of convex-hull determining linear systems, L, and P algorithms.

One of these, which solves the useful “Chinese Postman’s Problem”, is the
“optimum matching problem” in a graph G which is not necessarily bipartite,
i.e., the gay marriage problem, and the optimum gay marriage problem,
by algorithmically proving an easy description of “the matching polytope”.
This was hoped to be an ingredient for solving TSP, though apparently it is not.

In 1961 while working on combinatorial optimization problems in the
new Operations Research Section of the Mathematics Division of the
U.S. National Bureau of Standards, my wonderful mentor Alan Goldman arranged
through his wonderful Princeton mentor, Professor Tucker, thesis supervisor of
Nash’s equilibria and much else, for me to be a junior participant in a Summer
long workshop at the Rand Corporation, across from Muscle Beach in California.
Besides the utter novice me, seemingly every known combinatorist participated.
I needed a successful example of the NP idea, such as the non-bipartite matching
problem. The day before my scheduled lecture to the eminences I still did not
have it. Then Eureka, I did! You shrink blossoms! So the lecture was a success,
and attracted discussion. Professor Tucker offered me a job at Princeton, chairing
the Combinatorics and Games Seminar.

Very old non-bipartite matching “blossom algorithm” papers are on the internet.
Several good books on some P algs are called “Combinatorial Optimization”.
It seems that most of NP∩coNP successes are related to the marriage problem.

Another early P success, which led to matroid theory successes, was
a polynomial time way to solve a system of linear equations, Ax = b.
Well-known Gaussian elimination is not polynomial time
since the number of bits doubles as each column is treated.
The linear elimination algorithm in the very old paper,
Systems of Distinct Representatives and Linear Algebra, on the internet,
is polytime for integer entries but not with indeterminate symbol entries.
Thus there is a polynomial time randomized algorithm
for testing non-singularity of the matrix A by substituting integers for symbols.
The paper asks the great still unanswered question: Is there a polynomial time
deterministic algorithm for testing non-singularity of a matrix
with indeterminate symbol entries? It answers yes for certain cases
– in particular where the entries of A are zeroes and distinct symbols.
How? By the marriage problem algorithm.
What about when the symbolic entries of A are not all distinct?

Thanks. Please come to the course. Jack.