Есть ли теория, которая сочетает в себе теорию категорий / абстрактную алгебру и вычислительную сложность?

18

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


В качестве мотивирующего примера давайте рассмотрим моноиды. Хорошо известно, что если операция является моноидом, то мы можем распараллелить операцию.

Например, в Haskell, мы можем тривиально определить, что сложение является моноидом над целыми числами, например так:

instance Monoid Int where
    mempty = 0
    mappend = (+)

Теперь, если мы хотим вычислить сумму от 0 до 999, мы можем сделать это последовательно:

foldl1' (+) [0..999]

или мы могли бы сделать это параллельно

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel

Но распараллеливание этого моноида имеет смысл только потому, что mappend работает в постоянном времени. Что если бы это было не так? Например, списки - это моноиды, в которых mappend не запускает непостоянное время (или пространство!). Я предполагаю, что именно поэтому в Haskell нет функции параллельного mconcat по умолчанию. Наилучшая реализация зависит от сложности моноида.


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

Майк Избицкий
источник
1
Тип Integer в Haskell - это целые числа с множественной точностью, и временная сложность сложения с ними, естественно, зависит от длины входных целых чисел, поэтому неверно говорить, что mappend в вашем экземпляре Monoid для Integer выполняется в постоянное время.
Tsuyoshi Ito
@ TsuyoshiIto Вы правы, я хотел использовать Int. Исправлена.
Майк Избицкий
Вы видели этот вопрос ?
Каве
@Kaveh У меня не было, спасибо за указатель. Из быстрого прочтения звучит так, будто никто не занимался какой-либо теоретико-теоретической работой над самими классами сложности (и есть некоторые споры о том, что это могло бы вообще означать или если это стоящая цель). Поэтому я думаю, что это в значительной степени отвечает на первую часть моего вопроса и просто оставляет любые взаимодействия между алгеброй и сложностью.
Майк Избицкий
Много взаимодействия между алгеброй и теорией сложности. Есть даже книги под названием «Теория алгебраической сложности», в которых используются и применяются алгебраические концепции и методы для сложности. И есть также обширные работы, применяющие теорию сложности к алгебре. Вы должны быть более конкретными, чтобы получить ответ.
Каве

Ответы:

12

[Вычислительная сложность и теория категорий] кажутся такими естественными парами.

Учитывая выдающуюся вычислительную сложность как область исследований, если бы они были такими естественными собратьями, может кто-нибудь уже выявил бы связь?

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

Tзнак равноT1T2T3Tя,1 . Вместо этого мы создаем TM, определяя их два компонента отдельно: элемент управления (FSM) и ленту. Ни контроль, ни лента сами по себе не имеют хороших алгебр.

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

  • Склейте их вместе, как порядковое сложение. Это не правильное понятие, потому что ленты бесконечны, и, склеивая их как порядковое сложение, мы получаем двойной бесконечный объект, который выходит за пределы конечной вычислимости, что приводит к бесконечным вычислениям / гиперкомпьютерам, которые интересны как математические, но не соответствуют выполнимые вычисления.

  • Вставляйте их параллельно , например, две машины с 3 головками превращаются в машины с 6 головками. Это не говорит нам о том, как компоненты компьютеров взаимодействуют друг с другом.

  • Чередовать ленты. Одна из проблем этого подхода заключается в том, что неясно, каким может быть каноническое чередование, если оно есть. Более того, чередование «запутает» существующий элемент управления, который, как правило, точно настраивается на конкретную разметку ленты. Таким образом, мы не можем повторно использовать контроль напрямую.

π

В общем, мы довольно далеко от существенного алгебраического / категориального подхода к вычислительной сложности, и нам потребовалось бы несколько концептуальных достижений, чтобы достичь этого.


λπλπαλπ

Мартин Бергер
источник
Я бы сказал, что состав машин Тьюринга достаточно ясен, когда вы думаете о них как о абстрактных компьютерных программах. Естественный способ составления программ - называть одну подпрограммой другой. В более общем смысле, каждая программа является вычислимой в функции конечного времени и пространства, которая принимает определенный форматированный ввод и выводит другую форматированную строку, которая может быть передана в другую функцию. Вполне возможно, что некоторые входы мусора приведут к выводу мусора или что некоторые функции не будут выполняться в отведенное время и пространство, и в этом случае вся программа завершится сбоем.
Антон Фетисов
Очевидно, что не все программы могут быть скомпонованы таким образом, что естественно приводит нас к категории ТМ. Также вероятно, что следует отказаться от понятия пространственно-временного неограниченного ТМ, что в любом случае практически невозможно. Есть ли какое-либо опубликованное понятие, которое охватывает эту структуру?
Антон Фетисов
@AntonFetisov Вы пытались записать детали? Это не красиво.
Мартин Бергер
2

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

Моя собственная интерпретация этих результатов состоит в том, что точки синхронизации в словах различны для детерминированных и однозначных недетерминированных преобразователей и даже различны для детерминированных прямых и детерминированных обратных преобразователей. Принятие этой точки зрения точек синхронизации позволяет связать эти результаты с визуально выпадающими языками и поднимает вопрос, должны ли они также учитывать простые разделители (например, пробел или запятую) в дополнение к вызовам и возвратам. (Я предполагаю, что разделитель может быть эмулирован комбинированным вызовом return +, но поскольку для этого требуется два символа вместо одного, мне не ясно, достаточно ли этого. Могут также быть видимые языки, которые имеют только разделители, но не символы вызова или возврата.)

Томас Климпел
источник
Я сделал это вики-сообществом, потому что оно ссылается на мой собственный ответ на мой собственный вопрос, что, конечно, не очень хорошо. Я «чистил» свои любимые, и просто написать этот короткий ответ было проще всего.
Томас Климпел