Математический анализ и вычислительная сложность?

вычислительная сложность включает в себя большое количество комбинаторики и теории чисел, некоторые особенности стохастики и растущее количество алгебры.

Однако, будучи аналитиком, мне интересно, есть ли приложения анализа в этой области, или, может быть, идеи, вдохновленные анализом. Все, что я знаю, что немного соответствует этому, - это преобразование Фурье на конечных группах.

Вы можете помочь мне?

Флажолет и Седжвик опубликовали книгу «Аналитическая комбинаторика» http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html . Я не знаю много об этой теме, но люди на местах используют инструменты из сложного анализа. Пока что их приложения больше похожи на анализ алгоритмов, а не на вычислительную сложность, насколько я вижу.

Алгоритмы Маркова с цепочкой Монте-Карло являются полезным инструментом для нахождения алгоритмов аппроксимации. Некоторые методы для демонстрации того, что эти цепочки Маркова смешаны, основаны на анализе или основаны на нем, например, см. Главу об оценке объема выпуклого тела в книге Марка Джеррума о счетах .

Существуют аналитические подходы к лемме Семереди, которая имеет симпатичное применение для комбинаторного тестирования свойств. Лемма Семереди для аналитика имеет рандомизированный алгоритм для нахождения слабо регулярного разбиения графа; также см. Границы графика и тестирование параметров .

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

Для получения дополнительной информации хорошим источником является что-либо от Ассаф Наор .

Не о вычислительной сложности, но, тем не менее, интересно

Некоторые подходы к семантике бесконечных вычислений основаны на метрических пространствах. Погуглив "метрическую пространственную семантику", получается много. Одна (старая) ссылка на эту тему - это семантика потока управления де Баккера и де Винка. Некоторая недавняя работа была проделана нашим собственным Neel , а именно Ультраметрическая семантика для реактивных программ . Область очень отличается от описанной выше, но концепции анализа наверняка найдут здесь свое место.

Теория меры ограниченного ресурса, разработанная Джеком Латцем, является отличной областью для людей, которые имеют опыт анализа. Оригинальная статья

Почти везде высокая неравномерная сложность , Джек Х. Латц, Журнал компьютерных и системных наук, 1992.

обобщить понятие меры Лебега на классы сложности, и многие следующие работы можно найти в Интернете.

$\mathsf{P}$$\mathsf{NP}$$\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{ESPACE}$$\Omega(2^n/n)$$\mathsf{ESPACE}$

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

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

Вы также можете взглянуть на « Основы алгебры и анализа для информатики » Жана Галлье. Эта книга находится в разработке и рассказывает, что нового в этой области.

Я считаю, что лучшая связь между математическим анализом и теорией сложности заключается в реальной модели вычислений Блюма и др. По-прежнему остается открытой проблема отделения NP_R от P_R, где два класса определены в реальной модели вычислений, в которой каждое действительное число является сущностью, а одна регулярная операция (+, -, *, /) занимает один шаг.