On search decision and the efficiency of polynomial-time algorithms

摘要: Recent advances in well-partial-order theory, especially the seminal contributions of Robertson and Seymour, have troubling consequences for those who would equate tractability with polynomial-time decidability. Specifically: many problems are now known to be decidable low-degree polynomial time, but only by decision algorithms overwhelmingly astronomical constants proportionality,the existence such a algorithm alone does not ensure that corresponding search problem can solved efficiently, andeven if both shown computable, there is no guarantee correct found or even recognized within any bounded amount time.In this paper, we present number techniques dealing these remarkable features based on well-partially-ordered sets. Our main results include general strategy which made constructive. With aid method, demonstrate almost all catalogued applications RS posets. We also prove that, despite nonconstructive nature theory line research based, poset application settle P