|
Информация о статье
2003 г., Том 8, № 1, с.12-23
Лакеев А.В.
Вычислительная сложность оценки множеств обобщенного решения для интервальной линейной системы
В работе исследуется вычислительная сложность задач распознавания и оценивания обобщенных множеств решений интервальных систем линейных алгебраических уравнений. Показано, что если матрица системы содержит "достаточно много" элементов с интервальной неопределенностью Е-типа, то задачи распознавания и оценивания множества решений такой системы уравнений являются NP-трудными. Напротив, если в интервальной матрице системы присутствует "не очень много" Е-неопределенных элементов и большинство элементов имеет А-тип неопределеннос-ти, то эти задачи являются полиномиально разрешимыми.
[полный текст] Классификатор Msc2000:- *65G30 Интервальная и конечная арифметика
- 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
- 68Q25 Analysis of algorithms and problem complexity
Классификатор Computer Science:- *F.2 Analysis of Algorithms and Problem Complexity
- F.1.3 Complexity Measures and Classes
- G.1.0 General (Numerical Analysis)
Ключевые слова: контролируемое решение, квантификатор, легко вычислимая функция
Библиографическая ссылка:
Лакеев А.В. Вычислительная сложность оценки множеств обобщенного решения для интервальной линейной системы // Вычислительные технологии. 2003. Т. 8. № 1. С. 12-23
|
|
|
|
