Информационная сложность

Информационная сложность ( IBC ) изучает оптимальные алгоритмы и вычислительную сложность для непрерывных задач, возникающих в физике , экономике , инженерии и математических финансах . IBC изучал такие непрерывные задачи, как интегрирование по путям , уравнения в частных производных , системы обыкновенных дифференциальных уравнений , нелинейные уравнения , интегральные уравнения , неподвижные точки очень высокой размерности и интегрирование . Все эти проблемы связаны с функциями (обычно многомерными) действительной или комплексной переменной. Поскольку никогда нельзя получить решение интересующих задач в замкнутой форме, приходится довольствоваться численным решением. Поскольку функцию действительной или комплексной переменной невозможно ввести в цифровой компьютер, решение непрерывных задач требует частичной информации. Для простой иллюстрации: при численном приближении интеграла доступны только выборки подынтегральной функции в конечном числе точек. При численном решении уравнений в частных производных функции, задающие граничные условия и коэффициенты дифференциального оператора, могут быть только дискретизированы. Кроме того, получение этой частичной информации может оказаться дорогостоящим. Наконец, информация часто загрязнены шумом.

Целью информационной сложности является создание теории вычислительной сложности и оптимальных алгоритмов для решения задач с частичной, загрязненной и ценной информацией, а также применение результатов для ответа на вопросы в различных дисциплинах. Примеры таких дисциплин включают физику , экономику, математические финансы, компьютерное зрение , теорию управления , геофизику , медицинскую визуализацию , прогнозирование погоды и прогнозирование климата , а также статистику . Теория разрабатывается на абстрактных пространствах, обычно гильбертовых или банаховых пространствах, а приложения обычно предназначены для многомерных задач.

Поскольку информация частична и загрязнена, можно получить лишь приблизительные решения. IBC изучает вычислительную сложность и оптимальные алгоритмы приближенных решений в различных условиях. Поскольку настройка наихудшего случая часто приводит к отрицательным результатам, таким как неразрешимость и трудноразрешимость, также изучаются настройки с более слабыми гарантиями, такие как среднее, вероятностное и рандомизированное. Достаточно новой областью исследований IBC являются непрерывные квантовые вычисления .

Обзор

Мы проиллюстрируем некоторые важные концепции на очень простом примере: вычислении

$\int _{0}^{1}f(x)\,dx.$

Для большинства подынтегральных выражений мы не можем использовать фундаментальную теорему исчисления для аналитического вычисления интеграла; мы должны аппроксимировать его численно. Мы вычисляем значения $f$ в n точках

$[f(t_{1}),\dots ,f(t_{n})].$

Числа n представляют собой частичную информацию об истинном подынтегральном выражении. $f(x).$ Мы объединяем эти n чисел с помощью комбинаторного алгоритма для вычисления приближения к интегралу. Подробности см. в монографии «Сложность и информация» .

Поскольку у нас есть только частичная информация, мы можем использовать аргумент противника , чтобы сказать нам, насколько большим должно быть n для вычисления $\epsilon$-аппроксимация. Благодаря этим аргументам, основанным на информации, мы часто можем получить точные оценки сложности непрерывных задач. Для дискретных задач, таких как факторизация целых чисел или задача коммивояжера, нам приходится довольствоваться предположениями об иерархии сложности. Причина в том, что входные данные представляют собой число или вектор чисел и, таким образом, могут быть введены в компьютер. Таким образом, на информационном уровне обычно нет аргументов противника, а сложность дискретной проблемы редко известна.

Задача одномерного интегрирования была использована только для иллюстрации. Для многих приложений важным является многомерная интеграция. Число переменных исчисляется сотнями или тысячами. Число переменных может быть даже бесконечным; затем мы говорим об интеграции путей. Причина, по которой интегралы важны во многих дисциплинах, заключается в том, что они возникают, когда мы хотим узнать ожидаемое поведение непрерывного процесса. См., например, приложение к математическим финансам ниже.

Предположим, мы хотим вычислить интеграл в d измерениях (размеры и переменные используются взаимозаменяемо) и хотим гарантировать не более $\epsilon$ для любого подынтегрального выражения в некотором классе. Вычислительная сложность задачи, как известно, порядка $\epsilon ^{-d}.$ (Здесь мы подсчитываем количество вычислений функции и количество арифметических операций, так что это временная сложность.) Это заняло бы много лет даже для скромных значений $d.$ Экспоненциальная зависимость от d называется проклятием размерности . Мы говорим, что проблема неразрешима.

Мы заявили о проклятии размерности для интеграции. Но экспоненциальная зависимость от d возникает почти для каждой исследованной непрерывной задачи. Как мы можем попытаться победить проклятие? Есть две возможности:

• Мы можем ослабить гарантию того, что ошибка должна быть меньше $\epsilon$ (наихудший случай) и соглашайтесь на стохастическую уверенность. Например, мы можем потребовать, чтобы ожидаемая ошибка была меньше, чем $\epsilon$ (средняя настройка.) Другой возможностью является рандомизированная настройка. Для некоторых задач мы можем снять проклятие размерности, ослабив гарантию; для других мы не можем. Существует большая литература IBC о результатах в различных условиях; см. раздел «Где узнать больше» ниже.
• Мы можем использовать знания предметной области . См. «Пример: математические финансы» ниже.

Пример: математические финансы

Интегралы очень высокой размерности распространены в финансах. Например, расчет ожидаемых денежных потоков для обеспеченного ипотечного обязательства (CMO) требует расчета ряда $360$ размерные интегралы, $360$ это количество месяцев в $30$ годы. Напомним, что если требуется гарантия наихудшего случая, время имеет порядок. $\epsilon ^{-d}$ единицы времени. Даже если ошибка не маленькая, скажем $\epsilon =10^{-2},$ Это $10^{720}$ единицы времени. Люди, работающие в сфере финансов, уже давно используют метод Монте-Карло (MC), пример рандомизированного алгоритма. Затем в 1994 году исследовательская группа Колумбийского университета ( Папагеоргиу , Пасков, Трауб , Возняковски) обнаружила, что метод квази-Монте-Карло (QMC), использующий последовательности с низким расхождением, превосходит MC на один-три порядка. О результатах было сообщено ряду финансовых учреждений Уолл-стрит, что вызвало поначалу значительный скептицизм. Результаты были впервые опубликованы Пасковым и Траубом , Faster Valuation of Financial Derivatives , Journal of Portfolio Management 22, 113-120. Сегодня QMC широко используется в финансовом секторе для оценки производных финансовых инструментов.

Эти результаты являются эмпирическими; причем тут вычислительная сложность? QMC не является панацеей для всех интегралов большой размерности. Что особенного в производных финансовых инструментах? Вот возможное объяснение. $360$ измерения в CMO представляют собой ежемесячное время в будущем. Из-за дисконтированной стоимости денег переменные, представляющие времена в будущем, менее важны, чем переменные, представляющие ближайшие времена. Таким образом, интегралы неизотропны. Слоан и Возняковски представили очень мощную идею весовых пространств, которая является формализацией приведенного выше наблюдения. Они смогли показать, что благодаря этим дополнительным знаниям предметной области многомерные интегралы, удовлетворяющие определенным условиям, можно решить даже в худшем случае! Напротив, метод Монте-Карло дает только стохастическую уверенность. См. Слоана и Возняковского. Когда алгоритмы квази-Монте-Карло эффективны для многомерной интеграции? J. Complexity 14, 1-33, 1998. Для каких классов интегралов QMC превосходит MC? Это продолжает оставаться серьезной исследовательской проблемой.

Краткая история

Предшественники IBC могли быть найдены в 1950-х годах Кифером, Сардом и Никольским. В 1959 году Трауб понял, что оптимальный алгоритм и вычислительная сложность решения непрерывной задачи зависят от доступной информации. Он применил это понимание к решению нелинейных уравнений , что положило начало области теории оптимальных итераций. Это исследование было опубликовано в монографии 1964 года « Итеративные методы решения уравнений».

Общие условия информационной сложности были сформулированы Траубом и Возняковским в 1980 году в «Общей теории оптимальных алгоритмов». Список последних монографий и ссылки на обширную литературу см. в разделе «Подробнее» ниже.

Призы

Существует ряд премий за исследования IBC.

• Премия за достижения в области информационной сложности. Эта ежегодная премия, учрежденная в 1999 году, состоит из 3000 долларов США и мемориальной доски. Он вручается за выдающиеся достижения в области информационной сложности. Получатели указаны ниже. Принадлежность действительна на момент награждения.
  • 1999 Эрих Новак, Йенский университет, Германия
  • 2000 Сергей Переверзев, Украинская академия наук, Украина
  • 2001 Г.В. Васильковски, Университет Кентукки, США
  • 2002 Стефан Генрих, Университет Кайзерслаутерна, Германия
  • 2003 Артур Г. Вершульц, Фордхэмский университет, США
  • 2004 Питер Мате, Институт прикладного анализа и стохастики Вейерштрасса, Германия
  • 2005 Ян Слоан, профессор науки, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2006 Лешек Пласкота, факультет математики, информатики и механики, Варшавский университет, Польша
  • 2007 Клаус Риттер, факультет математики, Технический университет Дармштадта, Германия
  • 2008 Анаргирос Папагеоргиу, Колумбийский университет, США
  • 2009 Томас Мюллер-Гронбах, факультет компьютерных наук и математики, Университет Пассау, Германия
  • 2010 Болеслав З. Кацевич, факультет математики, Университет науки и технологий AGH, Краков, Польша
  • 2011 Айке Хинрихс, факультет математики и информатики, Йена, Германия
  • 2012 Майкл Гневух, факультет компьютерных наук, Университет Христиана-Альбрехта в Киле, Германия, и Школа математики и статистики Университета Нового Южного Уэльса, Сидней, Австралия
  • 2012 (Специальный приз) Кшиштоф Сикорский, факультет компьютерных наук, Университет Юты
  • Победители 2013 г.
    • Джозеф Дик, Университет Нового Южного Уэльса, Сидней, Австралия
    • Фридрих Пиллихшаммер, Университет Иоганна Кеплера, Линц, Австрия
  • 2014 Фрэнсис Куо, Школа математики, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2015 Питер Критцер, факультет финансовой математики, Университет Линца, Австрия
  • 2016 Фред Дж. Хикернелл, факультет прикладной математики, Технологический институт Иллинойса, Чикаго, США
  • Победители 2017 г.
    • Томас Кюн, Лейпцигский университет, Германия
    • Винфрид Зикель, Йенский университет, Германия.
  • 2018 Павел Пшибылович, Университет науки и технологий AGH в Кракове, Польша
  • 2019 Ян Выбирал, Чешский технический университет, Прага, Чехия
• Премия молодым исследователям за информационную сложность Эта ежегодная награда, учрежденная в 2003 году, состоит из 1000 долларов США и мемориальной доски. Получателями были
  • 2003 Фрэнсис Куо, Школа математики, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2004 Кристиан Лемье, Университет Калгари, Калгари, Альберта, Канада, и Джозеф Дик, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2005 Фридрих Пиллихшаммер, Институт финансовой математики, Университет Линца, Австрия
  • 2006 Якоб Крейциг, Дармштадтский технический университет, Германия и Дирк Нуйенс, Католический университет, Левен, Бельгия
  • 2007 Андреас Нойенкирх, Франкфуртский университет, Германия
  • 2008 Ян Выбирал, Йенский университет, Германия
  • 2009 Штеффен Дерайх, Берлинский технический университет, Германия
  • 2010 Даниэль Рудольф, Йенский университет, Германия
  • 2011 Питер Критцер, Университет Линца, Австрия
  • 2012 Павел Пшибилович, Университет науки и технологий AGH, Краков, Польша
  • 2013 Кристоф Айстляйтнер, кафедра анализа и вычислительной теории чисел, Технический университет Граца, Австрия
  • 2014 Тино Ульрих, Институт численного моделирования, Боннский университет, Германия
  • 2015 Марио Ульрих, Институт анализа, Университет Иоганна Кеплера, Линц, Австрия
  • 2016 Марио Хефтер, ТУ Кайзерслаутерн, Германия
  • Победители 2017 г.
    • Takashi Goda, University of Tokyo
    • Larisa Yaroslavtseva, University of Passau
  • 2018 Арнульф Йентцен, Швейцарский федеральный технологический институт (ETH), Цюрих, Швейцария
• Премия за лучшую статью, Journal of Complexity. Эта ежегодная награда, учрежденная в 1996 году, состоит из 3000 долларов (4000 долларов с 2015 года) и мемориальной доски. Многие, но далеко не все награды были присуждены за исследования IBC. Получателями были
  • 1996 Собака Паскаль
  • Победители 1997 года
    • Б. Банк, М. Джусти, Дж. Хайнц и ГМ Мбакоп
    • R. DeVore and V. Temlyakov
  • Победители 1998 года
    • Стефан Генрих
    • П. Кирринис
  • 1999 Артур Г. Вершульц
  • Победители 2000 г.
    • Бернард Моррен и Виктор Ю. Пэн
    • Ж. Морис Рохас
  • 2001 Эрих Новак
  • 2002 Питер Хертлинг
  • Победители 2003 г.
    • Маркус Блейзер
    • Болеслав Качевич
  • 2004 Стефан Генрих
  • Победители 2005 г.
    • Йосеф Йомдин
    • Йозеф Дик и Фридрих Пиллихшаммер
  • 2006 Кнут Петрас и Клаус Риттер
  • Победители 2007 г.
    • Мартин Авендано, Тереза ​​Крик и Мартин Сомбра
    • Иштван Беркес, Роберт Ф. Тичи и покойный Уолтер Филипп
  • 2008 Стефан Генрих и Бернхард Милла
  • 2009 Фрэнк Аурзада, Штеффен Дерайх, Михаэль Шутцов и Кристиан Формур
  • Победители 2010 г.
    • Айке Хинрикс
    • Симон Фукар, Ален Пажор, Хольгер Раухут, Тино Ульрих
  • Победители 2011 г.
    • Томас Лиф
    • Лешек Пласкота, Грег В. Васильковски
  • Победители 2012 г.
    • Dmitriy Bilyk, V.N. Temlyakov, Rui Yu
    • Лутц Кеммерер, Стефан Кунис, Дэниэл Поттс
  • Победители 2013 г.
    • Шу Тэдзука
    • Йоос Хайнц, Барт Куйперс, Андрес Рохас Паредес
  • 2014 Бернд Карл, Айке Хинрикс, Филипп Рудольф
  • 2015 Thomas Müller-Gronbach, Klaus Ritter, Larisa Yaroslavtseva
  • Победители 2016 г.
    • Дэвид Харви, Йорис ван дер Хувен и Грегуар Лесерф
    • Карлос Бельтран, Хорди Марсо и Хоаким Ортега-Серда
  • 2017 Мартейн Баартсе и Клаус Меер
  • Победители 2018 г.
    • Стефан Генрих
    • Юлиан Гроте и Кристоф Тале
  • Победители 2019 года
    • Айке Хинрикс, Йоша Прочно , Марио Ульрих

Ссылки

• Трауб, Дж. Ф., Итеративные методы решения уравнений, Prentice Hall, 1964. Переиздано издательством Chelsea Publishing Company, 1982; Русский перевод МИР, 1985; Переиздание Американского математического общества, 1998 г.
• Трауб Дж. Ф. и Возняковски Х. Общая теория оптимальных алгоритмов , Academic Press, Нью-Йорк, 1980 г.
• Трауб Дж. Ф., Возняковски Х. и Васильковски Г. В. Информация, неопределенность, сложность, Аддисон-Уэсли, Нью-Йорк, 1983 г.
• Новак Э., Детерминистические и стохастические границы ошибок в численном анализе, Конспект лекций по математике, том. 1349, Спрингер-Верлаг, Нью-Йорк, 1988 г.
• Трауб Дж. Ф., Возняковски Х. и Васильковски Г. В. (1988). Информационная сложность . Нью-Йорк: Академическая пресса. ISBN  978-0126975451 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Вершульц, А.Г., Вычислительная сложность дифференциальных и интегральных уравнений: информационный подход, Oxford University Press, Нью-Йорк, 1991 г.
• Ковальски М., Сикорски К. и Стенгер Ф., Избранные темы аппроксимации и вычислений, Oxford University Press, Оксфорд, Великобритания, 1995 г.
• Пласкота Л., Зашумленная информация и сложность вычислений, издательство Кембриджского университета, Кембридж, Великобритания, 1996 г.
• Трауб Дж. Ф. и Вершульц А. Г. Сложность и информация, Oxford University Press, Оксфорд, Великобритания, 1998 г.
• Риттер К. Анализ численных задач в среднем случае, Springer-Verlag, Нью-Йорк, 2000 г.
• Сикорски К., Оптимальное решение нелинейных уравнений, Oxford University Press, Оксфорд, Великобритания, 2001 г.

Обширную библиографию можно найти в монографиях N (1988), TW (1980), TWW (1988) и TW (1998).На веб-сайте IBC имеется база данных с возможностью поиска, содержащая около 730 позиций.

Внешние ссылки

• Журнал сложности
• Сложность и информация
• Джозеф Трауб
• Дж. Ф. Трауб, 1985. Введение в информационную сложность.