ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

6. Topology

1991 MS Classification: 57-XX Manifolds and cell complexes; 68-XX Computer Science; 81-XX Quantum Theory Freedman, Michael H. ; Microsoft Corporation, Redmond, WA, U. S. A. Topological views of computational complexity

Occasionally problems of fundamental importance arrive in mathematics from another field; usually from physics (differential equations, indefinite metrics, operator theory, generalized functions, attractors, instantons, strings); once from philosophy (self-reference); and now from computer science. I refer to the basic problem of computational complexity, most notably the conjecture that P ≠ NP. This is essentially the assertion that many standard decision problems, such as the existence of a 3-coloring of a graph, can not be decided on by a computation whose time grows only polynomially in the size of the instance (the graph in this example). A proof of this conjecture would be truly remarkable, as it must foreclose myriad yetunconceived approaches. Once appreciated, this thought has led many to wonder if the conjecture is undecidable. The notion of computational “time” is at least slightly model dependent, and the incorporation of quantum mechanical principles appears to allow models of computation which are dramatically faster—at least on certain problems—so P/NP becomes a family of related questions depending on the computational model. Mathematicians should think of the P/NP questions, not only as problems within mathematics, but as a threat to our practice of mathematics, for the unexpected outcome would imply the existence of a rapid, as opposed to exhaustive, algorithm for finding short proofs—the only kind of proof people can find anyway. The lecture will consist of observations which bring the perspective of topology to computational complexity. Possible topics include:

• A heuristic view of “decidability” in terms of “general position”.

• Logical and coloring problems as examples of TQFTs (Topological Quantum Field Theories).

• TQFTs as a possible bridge between physics and computation. The “observables” of the Witten-Jones Chern-Simons theory are #P -hard to compute, so if they could be instead measured (efficiently), #P - hard problems could be solved (rapidly). (#P is a class of problems with natural number answers, e. g., the number of 3-colorings of a graph, analogous to, but presumably more difficult than, NP.)

• “Finite-type” invariants of graphs and their relation to “hard” problems. The notion of finite-type invariant can be borrowed from topology and used in many combinatirial settings.

• A partial generalization of the satisfaction problem in Boolean logic which is amenable to “homological”, hence rapid, solution.