Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard |
| |
| Authors: | V. Kreinovich A. V. Lakeyev |
| |
| Affiliation: | (1) Department of Computer Science, University of Texas at El Paso, 79968 El Paso, TX;(2) Irkutsk Computing Center, Russian Academy of Science Siberian Branch, Lermontov Str. 134, 664033 Irkutsk, Russia |
| |
| Abstract: | It is proved that for every δ>0, if there exists a polynomial-time algorithm for enclosing solutions of linear interval equations with relative (or absolute) overestimation better than δ, then P=NP. The result holds for the symmetric case as well. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
