|
Article information
2003 , Volume 8, № 1, p.12-23
Lakeyev A.V.
Computational complexity of estimation of generalized solution sets for Interval Linear Systems
В работе исследуется вычислительная сложность задач распознавания и оценивания обобщенных множеств решений интервальных систем линейных алгебраических уравнений. Показано, что если матрица системы содержит "достаточно много" элементов с интервальной неопределенностью Е-типа, то задачи распознавания и оценивания множества решений такой системы уравнений являются NP-трудными. Напротив, если в интервальной матрице системы присутствует "не очень много" Е-неопределенных элементов и большинство элементов имеет А-тип неопределеннос-ти, то эти задачи являются полиномиально разрешимыми.
[full text] Classificator Msc2000:- *65G30 Interval and finite arithmetic
- 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
- 68Q25 Analysis of algorithms and problem complexity
Classificator Computer Science:- *F.2 Analysis of Algorithms and Problem Complexity
- F.1.3 Complexity Measures and Classes
- G.1.0 General (Numerical Analysis)
Keywords: controllable solution, quantifier, easy computable function
Author(s):
Lakeyev Anatoly Valentinovich
PhD. , Associate Professor
Position: Head of Laboratory
Office: Irkutsk Institute of systems dynamics and control theory SB RAS
Address: 664033, Russia, Irkutsk, Lermontov str., 134
Phone Office: (3952) 311390
E-mail: lakeyev@icc.ru
Bibliography link:
Lakeyev A.V. Computational complexity of estimation of generalized solution sets for Interval Linear Systems // Computational technologies. 2003. V. 8. № 1. P. 12-23
|
|
|
|
