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

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

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

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

• 1 Обзор
• 2 Пример: математические финансы
• 3 Краткая история
• 4 Призы
• 5 Ссылки
• 6 Внешние ссылки

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

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

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

$[f\; (t\; 1),\dots ,\; f\; (t\; n)].\; \{\backslash \; displaystyle\; [f\; (t\_\; \{1\}),\; \backslash \; dots,\; f\; (t\_\; \{n\})].\}$

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

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

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

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

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

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

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

Эти результаты являются эмпирическими; Причем тут вычислительная сложность? QMC не является панацеей от всех интегралов большой размерности. Что особенного в производных финансовых инструментах? Вот возможное объяснение. Измерения $360\; \{\backslash \; displaystyle\; 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 Томас Мюллер-Гронбах, Fakultaet fuer Informatik und Mathematik, Universitaet Passau, Германия
  • 2010 Болеслав З. Кацевич, факультет математики, Университет науки и технологий AGH, Краков, Польша
  • 2011 Aicke Hinrichs, Fakultä t für Mathematik und Informatik, FSU Jena, Germany
  • 2012 Michael Gnewuch, Департамент компьютерных наук, Christian-Albrechts-Universitaet zu Kiel, Германия, и Школа математики и статистики, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2012 (Специальный приз) Кшиштоф Сикорски, факультет компьютерных наук, Университет Юты
  • Победители 2013 года
    • Йозеф Дик, Университет Нового Южного Уэльса, Сидней, Австралия
    • Фридрих Пиллихсхаммер, Университет Иоганна Кеплера, Линц, Австрия
  • 2014 Фрэнсис Куо, Школа математики, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2015 Питер Критцер, Департамент финансовой математики, Университет Линца, Австрия
  • 2016 Фред Дж. Хикернелл, Департамент прикладной математики, Технологический институт Иллинойса, Чикаго, США
  • Победители конкурса 2017 года
    • Томас Кюн, Лейпцигский университет, Германия
    • Винфрид Зикель, Йенский университет, Германия.
  • 2018 Павел Пшибилович, Научный университет AGH Электронная промышленность и технологии в Кракове, Польша
  • 2019 Ян Вибираль, Чешский технический университет, Прага, Чешская Республика
• Премия молодых исследователей за информационную сложность Эта ежегодная премия, учрежденная в 2003 году, состоит из 1000 долларов и мемориальная доска. Получателями были
  • 2003 г. Фрэнсис Куо, Школа математики, Университет Нового Южного Уэльса, Сидней, Австралия
  • 2004 г. Кристиан Лемье, Университет Калгари, Калгари, Альберта, Канада, и Йозеф Дик., Университет Нового Южного Уэльса, Сидней, Австралия
  • 2005 г. Фридрих Пиллихсхаммер, Институт финансовой математики, Университет Линца, Австрия
  • 2006 г. Якоб Кройтциг, Технический университет Дармштадта, Германия, и Дирк Нуйенс, Университет Католике, Лёвен, Бельгия
  • 2007 Андреас Нойенкирх, Франкфуртский университет, Германия
  • 2008 Ян Вибираль, Йенский университет, Германия
  • 2009 Штеффен Дерих, технический университет Берлина, Германия
  • 2010 Даниэль Рудольф, Университет Йены, Германия
  • 2011 Питер Критцер, Университет Линца, Австрия
  • 2012 Павел Пржибилович, Университет науки и технологий AGH, Краков, Польша
  • 2013 Кристоф Айстляйтнер, Отдел анализа и теории вычислительных чисел, Технический университет Граца, Австрия
  • 2014 Тино Ульрих, Ins титул для численного моделирования, Боннский университет, Германия
  • 2015 Марио Ульрих, Институт анализа, Университет Иоганна Кеплера, Линц, Австрия
  • 2016 Марио Хефтер, Технический университет Кайзерслаутерн, Германия
  • Победители 2017 года
    • Такаши Года, Токийский университет
    • Лариса Ярославцева, Университет Пассау
  • 2018 Арнульф Йентцен, Eidgenössische Technische Hochschule (ETH) Цюрих, Швейцария
• Премия за лучшую бумагу, Journal of Complexity Эта ежегодная награда, учрежденная в 1996 году, состоит из 3000 долларов (с 2015 года - 4000 долларов) и плакетки. Многие, но далеко не все награды были присуждены за исследования в IBC. Получателями были
  • 1996 Паскаль Койран
  • Со-победители 1997 года
    • Б. Банк, М. Джусти, Дж. Хайнц и Г. М. Мбакоп
    • Р. Деворе и В. Темляков
  • Победители конкурса 1998 года
    • Стефан Генрих
    • П. Кирринис
  • 1999 Артур Г. Вершульц
  • Победители 2000 года
    • Бернар Моррен и Виктор Ю. Пэн
    • Дж. Морис Рохас
  • 2001 Эрих Новак
  • 2002 Питер Хертлинг
  • Победители 2003 года
    • Маркус Блейзер
    • Болеслав Кацевич
  • 2004 Стефан Генрих
  • Победители 2005 года
    • Йосеф Йомдин
    • Йозеф Дик и Фридрих Пиллихсхаммер
  • Кнут Петрас и Клаус Риттер 2006 года
  • Победители 2007 года
    • Мартин Авендано, Тереза ​​Крик и Мартин Сомбра
    • Иштван Беркес, Роберт Ф. Тихи и покойный Уолтер Филипп
  • 2008 Стефан Генрих и Бернхард Милла
  • 2009 Фрэнк Орзада, Штеффен Дерих, Майкл Шойцов и Кристиан Формор
  • Победители 2010 года
    • Айке Хинрикс
    • Саймон Фукар, Ален Паджор, Хольгер Раухут, Тино Ульрих
  • Победители 2011 года
    • Томас Даун
    • Лешек Пласкота, Грег В. Васильковски
  • Победители 2012 года
    • Дмитрий Билык, В.Н. Темляков, Руи Ю
    • Лутц Каммерер, Стефан Кунис, Дэниел Поттс
  • Победители 2013 года
    • Шу Тезука
    • Йоос Хайнц, Барт Куиджперс, Андрес Рохас Паредес
  • 2014 Бернд Карл, Айке Хинрикс, Филипп Рудольф
  • 2015 Томас Мюллер-Гронбах, Клаус Риттер, Лариса Ярославцева
  • Победители 2016 года
    • Дэвид Харви, Йорис ван дер Хувен и Грегуар Лесерф
    • Карлос Бельтран, Хорди Марсо и Хоаким Ортега-Серда
  • 2017 Мартин Баартсе и Клаус Меер
  • Победители конкурса 2018 года
    • Стефан Генрих
    • Джулиан Гроте и Кристоф Теле

• Трауб, Дж. Ф., Итерационные методы решения уравнений, Прентис Холл, 1964. Переиздано Chelsea Publishing Company, 1982; Русский перевод МИР, 1985; Переиздано Американским математическим обществом, 1998 г.
• Трауб, Дж. Ф., и Возняковски, Х., Общая теория оптимальных алгоритмов, Academic Press, Нью-Йорк, 1980
• Трауб, JF, Woniakowski, H., and Wasilkowski, GW, Information, Uncertainty, Complexity, Addison-Wesley, New York, 1983
• Novak, E., Детерминированная и стохастическая ошибка Границы в численном анализе, Лекции по математике, т. 1349, Springer-Verlag, New York, 1988
• Трауб, Дж. Ф., Возняковски, Х., и Васильковский, Г. У. (1988). Информационная сложность. Нью-Йорк: Academic Press. ISBN 978-0126975451. CS1 maint: несколько имен: список авторов (ссылка )
• Werschulz, AG, Вычислительная сложность дифференциальных и интегральных Уравнения: информационный подход, Oxford University Press, Нью-Йорк, 1991
• Ковальски, М., Сикорски, К., и Стенгер, Ф., Избранные темы приближения и вычислений, Oxford University Press, Oxford, UK, 1995
• Plaskota, L., Шумная информация и вычислительная сложность, Cambridge University Press, Кембридж, Великобритания, 1996
• Трауб, Дж. Ф., и Вершульц, А. Г., Сложность и информация, Oxford University Press, Оксфорд, Великобритания, 1998
• Риттер, К., Анализ среднего случая численных задач, Springer-Verlag, New York, 2000
• Sikorski, K., Optimal Solution of Nonlinear Equations, Oxford University Press, Oxford, UK, 2001

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

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