Computational complexity of optimization and crude range testing: a new approach motivated by fuzzy optimization

✍ Scribed by G.William Walster; Vladik Kreinovich

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 274 KB
• Volume: 135
• Category: Article
• ISSN: 0165-0114
• DOI: 10.1016/s0165-0114(02)00254-3

✦ Synopsis

It is often important to test whether the maximum max B f of a given function f on a given set B is smaller than a given number C. This "crude range testing" (CRT) problem is one of the most important problems in the practical application of interval analysis. Empirical evidence shows that the larger the di erence C -max B f, the easier the test. In general, the fewer global maxima, the easier the test; and ÿnally, the further away global maxima are from each other, the easier the test. Using standard complexity theory to explain these empirical observations fails because the compared CRT problems are all NP-hard. In this paper the analysis of fuzzy optimization is used to formalize the relative complexity of di erent CRT problems. This new CRT-speciÿc relative complexity provides a new and "robust" theoretical explanation for the above empirical observations. The explanation is robust because CRT relative complexity takes numerical inaccuracy into consideration. The new explanation is important because it is a more reliable guide than empirical observations to developers of new solutions to the CRT problem.