Mr. Fellows et Ma. Langston, ON SEARCH, DECISION, AND THE EFFICIENCY OF POLYNOMIAL-TIME ALGORITHMS, Journal of computer and system sciences, 49(3), 1994, pp. 769-779
Citations number
17
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
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.