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

Препринт

On a Class of Optimization Problems with No 'Effectively Computable' Solution

Как известно, макроскопические свойства больших случайных объектов могут быть не случайными. Мы демонстрируем этот эффект для некоторого специального класса случайных оптимизационных задач большого размера, связанных с известной вычислительной проблемой нахождения максимального числа одновременно удовлетворяемых уравнений заданной переопределенной системы линейных уравнений. Задача такого рода возникает перед Агентом, который хочет построить дом, максимально защищенный от возможных стихийных бедствий. В таких задачах Агент не имеет эффективно вычислимых оптимальных решений. Мы устанавливаем, что ``равномерная'' смешанная стратегия (использование с одинаковой вероятностью всех чистых стратегий) при достаточно большом  размере задачи близка к оптимальному решению с вероятностью близкой к единице. Более того, мы показываем, что не существует эффективно вычислимой стратегии существенно лучшей для всех задач рассматриваемого класса