"Записки научных семинаров ПОМИ"
Том 436, стр. 122-135
Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений
М. Р. Гаврилович, В. Л. Крепс
Национальный исследовательский университет
``Высшая школа экономики'',
ул. Союза Печатников, д. 16,
190008 С.-Петербург, Россия
mishap@sdf.org
vita-kreps@mail.ru
- Аннотация:
Как известно, большие случайные структуры имеют неслучайные
макроскопические свойства. Мы приводим пример
неслучайных \break свойств для класса больших оптимизационных задач,
связанных с вычислительной проблемой $MAX\, FLS^=$ вычисления
максимального числа совместных уравнений в данной переопределенной
системе линейных уравнений. Для этого класса мы доказываем следующее.
Не существует ``эффективно вычислимой'' оптимальной стратегии.
При стремлении размера случайной задачи к бесконечности
вероятность того, что равномерная смешанная стратегия оптимальна,
стремится к единице. Более того, нет ``эффективно вычислимой''
стратегии, дающей существенно лучший результат для
каждого примера оптимизационной задачи.
Библ. -- 13 назв.
- Ключевые слова:
oптимизация, концентрация меры, вероятностно
проверяемые доказательства
[optimization, concentration of measure, probabilistically
checkable proofs]
Полный текст(.pdf)