ON SEARCH, DECISION, AND THE EFFICIENCY OF POLYNOMIAL-TIME ALGORITHMS

Recent advances in well-quasi-order theory have troubling consequences for those who would equate tractability with polynomial-time complexity. In particular, there is no guarantee that polynomial-time algorithms can be found just because a problem has been shown to be decidable in polynomial time. We present techniques for dealing with this unusual development. Our main results include a general construction strategy with which low-degree polynomial-time algorithms can now be produced for almost all of the catalogued algorithmic applications of well-quasi-order theory. We also prove that no such application of this theory can settle N (Is this statement true?) N P nonconstructively by any established method of argument. (C) 1994 Academic Press, Inc.