𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On search, decision, and the efficiency of polynomial-time algorithms

✍ Scribed by Michael R. Fellows; Michael A. Langston

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
622 KB
Volume
49
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 Jg ~ Jg'~ nonconstructively by any established method of argument.

πŸ“œ SIMILAR VOLUMES

On the efficiency of polynomial time app
On the efficiency of polynomial time approximation schemes
✍ Marco Cesati; Luca Trevisan πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 630 KB

A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and E > 0 find;,; (1 + E)-approximate solution in time that is polynomial for each fixed E. Typical running times are no(+) or 2"' n. While algorithms of the former kind t

A real time algorithm for the location s
A real time algorithm for the location search of discontinuous conductivities with one measurement
✍ Ohin Kwon; Jin Keun Seo; Jeong-Rock Yoon πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 292 KB

## Abstract We consider an inverse problem for finding the anomaly of discontinuous electrical conductivity by one current‐voltage observation. We develop a real time algorithm for determining the location of the anomaly. This new idea is based on the observation of the pattern of a simple weighted