• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений

Как известно, большие случайные структуры имеют неслучайные макроскопические свойства. Мы приводим пример неслучайных \break свойств для класса больших оптимизационных задач, связанных с вычислительной проблемой $MAX\, FLS^=$ вычисления максимального числа совместных уравнений в данной переопределенной системе линейных уравнений. Для этого класса мы доказываем следующее. Не существует ``эффективно вычислимой'' оптимальной стратегии. При стремлении размера случайной задачи к бесконечности вероятность того, что равномерная смешанная стратегия оптимальна, стремится к единице. Более того, нет ``эффективно вычислимой'' стратегии, дающей существенно лучший результат для каждого примера оптимизационной задачи.