cfry@watdcsu.waterloo.edu (C.Fry - Inst. Computer Research) (10/12/88)
On Algorithmic Applications of Well-Partial-Order Theory
and Constructive Search Complexity
by
Michael A. Langston
of
Department of Computer Science
Washington State University
Pullman, WA 99164-1210
Abstract
I shall demonstrate how recent advances in the theory of well-
partially-ordered sets can be employed to prove the existence of
decision algorithms with low-degree polynomial running times for
a number of seemingly difficult combinatorial problems. Some of
these problems were not previously known to be in P at all; oth-
ers were only known to be in P by way of brute force or dynamic
programming formulations with unboundedly high-degree polynomial
running times. The methods I shall describe include the applica-
tion of the powerful Robertson-Seymour theorems on the well-
partial-ordering of graphs under both the minor and immersion
orders.
I shall also discuss the complexity of associated search prob-
lems, presenting a general line of attack that interleaves self-
reduction with obstruction testing to identify correct algo-
rithms. Curiously, this approach can extended, using a novel
idea originally suggested by Levin, so that (in principle) one
can write down an algorithm that is guaranteed to run in
asymptotically-optimal time even though its time complexity can-
not be deduced from its description or its behavior. An in-
teresting corollary of all this is that if the inherently Inon-
constructive tools from well-partial-order theory should be used
to prove P=NP (admittedly an unlikely event, but one with the po-
tential to render NP-completeness proofs useless as polynomial-
time algorithms), then the aforementioned approach insures a con-
structive proof as well. This talk reflects work performed
jointly with Michael R. Fellows.
DATE: Wednesday, October 19, 1988
TIME: 3:30 p.m.
PLACE: University of Waterloo, Davis Centre, Room 1302
Everyone is welcome. Refreshments served.