Есть ли какие-то темы в теоретической CS, которые больше касаются чистой математики?

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

Единственной вещью, которую я мог найти, была теория второстепенного графа, просматривая списки принятия топ-конференций. Но это не считается для меня «областью», на которой я могу сосредоточиться.

Вот еще три поля, которые соответствуют вашим критериям.

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

• Логика , особенно теория доказательств. Связи с информатикой слишком много, чтобы назвать, но логика не только богатая область чистой математики, но и основа математики.

• Теория чисел , «королева математики», которая считалась лишенной приложений ... пока не появилась криптография.

Да: теория графов, вычислительная геометрия, теория сложности, комбинаторика - вот что я исследую в CS. Векторные пространства и теория меры могут быть полезны и в теоретическом машинном обучении.

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

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

• Теория геометрической сложности является чрезвычайно «математической», и многие из ее ведущих исследователей являются более математиками. см., например, Теория геометрической сложности: введение для геометров / Ландсберг
• Теория групп тесно связана с TCS, например, при изучении проблемы слова, изоморфизмов и неразрешимости. см., например, ПРОБЛЕМА СЛОВА И ПРОБЛЕМА ИЗОМОРФИЗМА ДЛЯ ГРУПП / Стиллвелл
• некоторые теории автоматов очень математичны, например, связь полугрупп с датчиками конечных состояний и т. д., см., например, Математические основы теории автоматов / Пин

$\mathbb{B}$$\mathbb{F}_2$

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

Чтобы сказать немного больше о теории геометрической сложности (GCT): это применение алгебраической геометрии и теории представлений к долгосрочной программе для решения P против NP. Вопросы, поднятые в GCT, как правило, представляют собой глубокие математические вопросы, некоторые из которых уходят более чем на 100 лет назад к пионерам алгебраической геометрии и теории представлений - по-видимому, не имеют ничего общего с вычислениями, но с помощью GCT видно, что они на самом деле тесно связаны с вычислительной сложностью - и другие из которых поднимают новые вопросы и идеи в чистой математике (опять же, алгебраическая геометрия и теория представлений).

Не совсем теоретическая тема CS, но использует много результатов из теоретической CS: вас может заинтересовать верификация программного обеспечения, целью которой является обеспечение того, чтобы программа делала то, что должна, и ничего больше. Среди различных методов в этой теме некоторые особенно ориентированы на математику. Многие критические системы, в частности авионика / пространственная / ядерная, были доказаны таким образом, чтобы гарантировать, что они не содержат ошибок.

Многие математические поля вовлечены: логика, теория доказательств, теория автоматов, теория множеств, ...