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 complexi ty. In particular, there is no guarantee that polynomial-time algorith ms can be found just because a problem has been shown to be decidable in polynomial time. We present techniques for dealing with this unusua l development. Our main results include a general construction strateg y with which low-degree polynomial-time algorithms can now be produced for almost all of the catalogued algorithmic applications of well-qua si-order theory. We also prove that no such application of this theory can settle N (Is this statement true?) N P nonconstructively by any e stablished method of argument. (C) 1994 Academic Press, Inc.