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

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