Информационная сложность - Information-based complexity

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

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

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

Обзор

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

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

Для большинства интегрантов мы не можем использовать основная теорема исчисления вычислить интеграл аналитически; мы должны приблизить это численно. Вычисляем значения ${displaystyle f}$ в п точки

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

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

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

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

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

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

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

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

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

Эти результаты эмпирически; Причем тут вычислительная сложность? QMC не является панацеей от всех интегралов большой размерности. Что особенного в производных финансовых инструментах? Вот возможное объяснение. В ${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 Айке Хинрихс, Fakultät für Mathematik und Informatik, БСС, Йена, Германия
  • 2012 Майкл Гневух, Департамент компьютерных наук, 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 Тино Ульрих, Институт численного моделирования, Боннский университет, Германия
  • 2015 Марио Ульрих, Институт анализа, Университет Иоганна Кеплера, Линц, Австрия
  • 2016 Марио Хефтер, Технический университет Кайзерслаутерн, Германия
  • Победители 2017 года
    • Такаси Года, Токийский университет
    • Лариса Ярославцева, Университет Пассау
  • 2018 Арнульф Йентцен, Высшая техническая школа Eidgenössische (ETH), Цюрих, Швейцария
• Премия за лучшую работу, Журнал сложности Эта ежегодная награда, учрежденная в 1996 году, состоит из 3000 долларов (4000 долларов с 2015 года) и мемориальной доски. Многие, но далеко не все награды были присуждены за исследования в 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. Переиздано "Челси Паблишинг Компани", 1982; Русский перевод МИР, 1985; Переиздано Американского математического общества, 1998 г.
• Трауб, Дж. Ф., Возняковски, Х., Общая теория оптимальных алгоритмов, Academic Press, Нью-Йорк, 1980 г.
• Трауб, Дж. Ф., Возняковски, Х., Васильковский, Г. В., Информация, Неопределенность, Сложность, Эддисон-Уэсли, Нью-Йорк, 1983 г.
• Новак Э., Детерминированные и стохастические границы ошибок в численном анализе, Краткие лекции по математике, т. 1349, Спрингер-Верлаг, Нью-Йорк, 1988
• Трауб, Дж. Ф., Возняковский, Х., Васильковский, Г. У. (1988). Информационная сложность. Нью-Йорк: Academic Press. ISBN  978-0126975451.
• Вершульц, А.Г., Вычислительная сложность дифференциальных и интегральных уравнений: информационный подход, 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). Сайт МДС имеет доступную для поиска базу данных, содержащую около 730 наименований.

внешняя ссылка

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