Приложения TCS к классической математике?

60

Мы в TCS часто используем мощные результаты и идеи из классической математики (алгебра, топология, анализ, геометрия и т. Д.).

Каковы некоторые примеры того, когда это пошло наоборот?

Вот некоторые из них, о которых я знаю (а также чтобы дать представление о типе результатов, о которых я спрашиваю):

Кубические пены (Гай Киндлер, Райан О'Доннелл, Ануп Рао и Ави Вигдерсон: сферические кубы и скругления в больших измерениях, FOCS 2008)
Программа теории геометрической сложности. (Хотя это технически является приложением алгебраической геометрии и теории представлений к TCS, они привели к введению новых квантовых групп и новых чисто алгебро-геометрических и теоретико-представительных идей в их стремлении к P против NP.)
Работа над метрическими вложениями, основанная на алгоритмах аппроксимации и результатах не приближаемости

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

reference-request big-list Joshua Grochow
источник

1

Это немного сложно ответить. Комбинаторика выходит за пределы классической математики?

Арнаб

2

Комбинаторика, безусловно, классическая математика, но я думаю, что тот же комментарий относится и к комбинаторике, и к логике. Итак, конечно, гипотеза Kakeya с конечным полем является хорошим примером, в то время как новые комбинаторные проекты, мотивированные PRGs, больше на заборе.

Джошуа Грохов

Вы можете найти хорошие примеры, посмотрев результаты, опубликованные, например, в Annals of Math сообществом TCS.

MCH

32

Расширители были разработаны в значительной степени в TCS, и они имеют глубокие связи и приложения к математике.

Gil Kalai
источник

22

Существует доказательство Двира гипотезы конечного поля какейя.

Dai Le
источник

3

Это было вызвано проблемой извлечения / слияния (см. Более позднюю статью Зеев и Ави Вигдерсон). Дальнейшие улучшения (Мадху Судан, Шубханги Сараф, Свастик Коппарти и Зеев Двир) использовали больше идей из теоретической информатики, в частности, из списка декодирования кодов (метод множественности).

Дана Мошковиц

1

Два замечания. Алгебраический метод, используемый Двиром, является одним из методов, используемых для решения классической задачи о расстояниях для плоских множеств. terrytao.wordpress.com/2010/11/20/… и gilkalai.wordpress.com/2010/11/20/… .

Гил Калай

2

Во-вторых, методы инцидентности и результаты вычислительной и дискретной геометрии имели более ранние применения к (реальной) проблеме Какейи.

Гил Калай

20

Милый пример, который я знаю, - это работа Майкла Фридмана под названием « Классы сложности как математические аксиомы », в которой описывается в области топологии 3-многообразий. $P^{\sharp P}\neq NP$

оборота Зейю
источник

20

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

Шумоустойчивость функций с низким влиянием: инвариантность и оптимальность Э. Моссель, Р. О'Доннелл, К. Олешкевич. Анналы математики 171 (1), с. 295-341 (2010). FOCS '05.

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

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

Улучшенное тестирование при низкой степени и его приложения . С. Арора и М. Судан. В ACM STOC 1997.

Субконстантный тест с низкой степенью вероятности ошибки и субконстантная характеристика вероятности ошибки PCP Н.П.

Дана Мошковиц
источник

19

Хотя я и предвзят, я думаю, что было бы справедливо сказать, что различные идеи из TCS способствовали прогрессу в обратной гипотезе для нормы Гауэрса, см., Например, статью Грина и Тао .

Manu
источник

7

Также справедливо сказать, что на компоненты доказательства для теоремы Семереди с помощью леммы о регулярности гиперграфа (Гауэрс, Тао, Родл, Шахт и др.) Повлияла работа Алона, Фишера, Шапиры и других в разработке более сильных версий лемма регулярности графа для доказательства тестируемости свойств графа.

Арнаб

18

Является ли теория вычислимости частью TCS? Если это так, то в качестве примера можно привести теорию вычислимости и дифференциальную геометрию Боба Соаре, которая демонстрирует применение результатов, полученных им с помощью Csima.

Не знаю, почему ссылка не отображается .... Здесь: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Аарон Стерлинг
источник

2

Независимо от того, считаете ли вы вычислимость частью TCS, мне нравится этот пример, о котором я просто забыла упомянуть. Это даже круче, потому что это можно сделать, используя сложность Колмогорова :).

Джошуа Грохов

17

Экстракторы это еще одно место, чтобы посмотреть. Например, статья Barak-Kindler-Shaltiel-Sudakov-Wigderson'04 дает (среди прочего) улучшенные построения графов Рамсея (проблема, которая была открыта некоторое время в дискретной математике).

Мориц
источник

15

De Wolf и Друкер упомянуть в своем обзоре на квантовых доказательствах о неожиданной связи между квантовым запросом сложности и -аппроксимация симметричных функций полиномами. $\epsilon$

оборота ильяраз
источник

13

Конструкция расширителя Zig-Zag использовалась для построения различных интересных примеров групп с некоторыми неожиданными свойствами, см. Мешулам-Вигдерсон , Розенман-Шалев-Вигдерсон . Сама конструкция очень интересна с чисто математической точки зрения, так как она использовала совершенно другие инструменты (мотивированные CS-точкой зрения на энтропию) для построения расширителей, чем предыдущие конструкции. (Однако, пожалуй, наиболее известное приложение находится внутри алгоритма пространства журналов TCS- Reingold для ненаправленной связи .)

Боаз Барак
источник

10

Позвольте мне упомянуть еще пару приложений:

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

Понятие вероятностного доказательства: здесь я не имею в виду вероятностный метод (который уходит корнями в математику, но имеет много применений к CS), а скорее тот факт, что математическое утверждение, такое как утверждение, требующее определенного числа, является простым, может получить доказательство "вне всякого разумного сомнения". Это концептуальный прорыв, пришедший из CS, хотя он еще не нашел применения в практике математики.

Гил Калай
источник

1

Я не знал, что другие области математики использовали идею сокращений значительно. Буду очень признателен за любые ссылки или указатели на такие работы! Кроме того, у меня сложилось впечатление, что вероятностные доказательства исходят из чистой комбинаторики, а не TCS?

Джошуа Грохов

3

Я объяснил, что я имею в виду под «вероятностным доказательством» в отредактированной версии моего ответа. Что касается сокращений: вычислительная сложность является областью математики, уходящей корнями в информатику. Одной из характеристик этой области является использование сокращений, которые играют важную роль на концептуальном и техническом уровне. Это гораздо более развито, чем аналогичные методы в других областях математики. Таким образом, искусство сокращений в TCS можно рассматривать как основное приложение TCS к математике. Я думаю, что сокращения типа CS повлияли на математиков и в других областях, и многое еще впереди.

Гил Калай

Джошуа, позвольте мне привести аналогию. Предположим, что кто-то называет «исчисление» одним из величайших приложений физики в классической математике. Можно также сказать, что исчисление главным образом важно для решения проблем, исходящих от физики, которые раньше не были «классической математикой». Тем не менее я думаю, что исчисление является основным вкладом физики в математику. Точно так же сокращения типа, используемого в теории сложности, является основным вкладом TCS в математику. В нем описывается основной математический аппарат и математические идеи, которые имеют самостоятельную ценность. (Не так важно, как исчисление, хотя.)

Гил Калай

@JoshuaGrochow Многие доказательства начинаются с чего-то вроде: «Мы можем предположить, что связан, поскольку число виджетов в графе является суммой / произведением количества виджетов в каждом компоненте», и часто более сложные версии этого вида идея. Считается ли это сокращением общей проблемы до связанной проблемы? С другой стороны, математики, вероятно, делали это задолго до появления теории вычислительной сложности.

G

$G$

Дэвид Ричерби

1

@JoshuaGrochow нетрудно найти нетривиальные примеры «общего случая к специальным сокращениям». Например, опрос Cassaza, который я связал в своем ответе, содержит тонны нетривиальных сокращений между задачами, эквивалентными проблеме Кадисона-Зингера, некоторые из которых на первый взгляд очень ограничены. Насколько я понимаю, арифметическая геометрия полна таких вещей, вы можете знать больше. Я не уверен, в какой степени TCS может претендовать на кредит за внедрение этого подхода к неразрешимым проблемам.

Сашо Николов

9

В конструктивном доказательстве Мозера локальной леммы Ловаша используются идеи информатики, дается новое доказательство локальной леммы Ловаша и решается проблема, о которой люди думали уже довольно давно.

Питер Шор
источник

9

Метод барьерных функций Батсона-Шпильмана-Шриваставы имел ряд применений в геометрии и функциональном анализе, возник в компьютерной науке и является очень оригинальной формой аргумента потенциальной функции, напоминающей метод пессимистических оценок. Более того, это противоречит общепринятому мнению, что анализ характеристического полинома случайных матриц неразрешим, и вместо этого лучше смотреть на моменты матрицы.

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

Однако, помимо спарсификаторов, этот метод имеет множество применений, многие из которых рассматриваются Ассафом Наором в этой статье . Некоторыми яркими примерами являются построение взвешенных графов расширителей, приближенные разложения Джона тождества с меньшим количеством точек, уменьшение размерности подмножеств / подпространств , версия принципа ограниченной обратимости и Цафрири. Для всех вышеперечисленных применений метод барьерных функций дает по существу жесткие границы, дает эффективный детерминистический алгоритм в дополнение к доказательству существования и часто обеспечивает более элементарное доказательство, чем предыдущие методы (хотя и не без сложных вычислений). $\ell_1^n$

Перенесемся в 2013 год, и метод барьерных функций на стероидах, дополненный механизмом чередования полиномов, был использован Маркусом, Шриваставой и Спилманом для решения одной из самых печально известных проблем функционального анализа - проблемы Кадисона-Зингера , Эта проблема возникает из фундаментальных вопросов математической физики, но она идет гораздо дальше - известно, что она эквивалентна десяткам задач по всей математике. Не говоря уже о том, что многие аналитики (в том числе Кадисон и Сингер) даже не думали, что проблема имеет положительное решение (цитируемое исследование Cassaza et al. Предполагает наличие возможных контрпримеров).

Сашо Николов
источник

5

Один из примеров, который приходит на ум, - это теорема вложения Хигмана и ее теоретико-групповые следствия.

Теорема Хигмана о вложении: группа G конечно порождена с рекурсивным представлением, если G является подгруппой конечно представленной группы.

(Обратите внимание, что левая часть эквивалентности имеет вычислительную составляющую, в то время как правая является чисто теоретико-групповой).

майк
источник

1

Эта связь также была расширена до сложности: недетерминированная временная сложность проблемы слова в любой группе полиномиально связана с наименьшей изопериметрической функцией (Дена) из любой конечно представленной группы в которую можно вложитьВ частности, тогда и только тогда, когда может быть вложена в конечно определенную группу с не более чем полиномиальной изопериметрической функцией. Биргет, Ольшанки, Рипс и Сапир, Анналы математики. 2002 ams.org/mathscinet-getitem?mr=1933724

G

$G$

H

$H$

G

$G$

W o r d (G) \in N P

$Word(G) \in NP$

G

$G$

Джошуа

5

Значение случайности , то, что считается «случайной последовательностью», и связанные вопросы были важны в математике, теории вероятностей и статистике на протяжении веков. Теоретическая информатика (и теория сложности) предлагает очень надежные глубокие и убедительные идеи для понимания случайности.

В то время как вероятностный метод начался в математике, дерандомизация, которая является важной математической концепцией, в основном разработана в CS.

Это связано с ответом Морица .

Гил Калай
источник

5

Теория автоматов и алгебраичность

Теория автоматов дала некоторые интересные результаты для характеристики алгебраичности. Я упоминаю два из них со ссылками. Это ни в коем случае не является исчерпывающим.

$\mathbb F_q(t)$

$\mathbb F_q(t)$ $q$ $q=p^s$ $p$ $s$ $\mathbb F_q[[t]]$ $\mathbb F_q$

$\mathbb F_q(t)$ $\mathbb F_q(t)$

$\sum_{i=0}^{\infty} a_i t^i$ $\mathbb F_q(t)$ $\{a_i\}_{i=0}^\infty$ $p$

$\mathbb F_q(t)$

\sum_{i \in I} x_{i} t^{i},

$\sum_{i\in I} x_i t^i\text,$

I

$I$

Q

$\mathbb Q$

F_{q} (t)

$\mathbb F_q(t)$

$\sum_{i\in I} a_i t^i$ $\mathbb F_q(t)$ $\{a_i\}_{i\in I}$ $p$

2. Трансцендентные числа

Автоматические последовательности также используются для характеристики трансцендентных чисел. Например,

$b$ $\ge 2$ $x\in\mathbb R$ $\mathbf x=\{x_i\}_{i=0}^\infty$ $b$

$\mathbf x$ $x$
$\mathbf x$ $b$ $x$
$x$

Конечно, первый пункт - это очень классический результат!

Рекомендации.

[1] Жиль Кристоль. Ensembles presque périodiques k-разведывательные . В теоретической информатике 9 (1), с. 141-145, 1979.

[2] Киран С. Кедлая. Конечные автоматы и алгебраические расширения функциональных полей . В Journal of théorie des nombres de Bordeaux 18 , pp 379-420, 2006. arXiv: math / 0410375 .

[3] Борис Адамцевский, Ян Буго. О сложности алгебраических чисел I. Разложения в целочисленные базисы . В Анналах математики 165 (2), с. 547-565, 2007.

Bruno
источник

Теорема (Adamczewski & Bugeaud [3]) может быть неверной или неправильно понятой

XL _At_Here_There

4

$L$ $\tau$

$L$

$\tau$ $p$ $\tau$ $(1+\tau)^c$ $c$

Bruno
источник

1

ИМХО TCS - это раздел математики, и я бы сказал, немного шире. Мы живем в алгоритмическом веке, почти каждый во всей человеческой деятельности изобретает / заново изобретает алгоритмы, в основном эвристику. Но некоторые из этих алгоритмов 1. хороши; 2. содержать (похоронить) ответы на глубокие математические вопросы; 3. Ждите профессионального математического анализа / улучшения / внимания. Мой личный опыт: потрясающая сила одной эвристики физики / машинного обучения, а именно аппроксимации Бете, в качестве техники доказательства. Основная проблема заключается в том, что возможные встречи такого рода в основном происходят в отрасли, где никого не волнуют эти не связанные с продуктом идеи / откровения.

Леонид Гурвиц
источник

Приложения TCS к классической математике?

Ответы:

Теория автоматов и алгебраичность

Fq(t)Fq(t)\mathbb F_q(t)

2. Трансцендентные числа

$\mathbb F_q(t)$