Теория категорий и абстрактная алгебра имеют дело со способом, которым функции могут быть объединены с другими функциями. Теория сложности имеет дело с тем, насколько сложно вычислить функцию. Мне странно, что я не видел, чтобы кто-нибудь совмещал эти области изучения, поскольку они кажутся такими естественными парами. Кто-нибудь делал это раньше?
В качестве мотивирующего примера давайте рассмотрим моноиды. Хорошо известно, что если операция является моноидом, то мы можем распараллелить операцию.
Например, в 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 по умолчанию. Наилучшая реализация зависит от сложности моноида.
Кажется, должен быть удобный способ описать различия между этими двумя моноидами. Затем мы должны иметь возможность комментировать наш код с этими различиями и иметь программы автоматически выбирать лучшие алгоритмы для использования в зависимости от сложности моноида.
источник
Ответы:
Учитывая выдающуюся вычислительную сложность как область исследований, если бы они были такими естественными собратьями, может кто-нибудь уже выявил бы связь?
Дикие спекуляции. Позвольте мне развлечь читателя мыслями о том, почему категоричное представление сложности вычислений сложно. Возможно, ключевой концептуальный кластер в теории категорий сосредоточен вокруг универсальных конструкций / свойств (со связанным аппаратом функторов, естественных преобразований, присоединений и т. Д.). Если мы можем показать, что математическая конструкция обладает универсальным свойством, это дает много понимания. Поэтому, если бы мы хотели категоричный подход к сложности вычислений, нам нужно было бы найти удобную категорию и показать, как ключевые понятия теории сложности (например, LOGSPACE или NP-hardness) могут быть заданы универсальными конструкциями, использующими эту категорию. Это еще не сделано, и я думаю, что это потому, что это действительно сложная проблема.
Давайте сначала посмотрим на ленты. Существует несколько естественных способов составления лент, но ни один из них не подходит для составного описания ТМ.
Склейте их вместе, как порядковое сложение. Это не правильное понятие, потому что ленты бесконечны, и, склеивая их как порядковое сложение, мы получаем двойной бесконечный объект, который выходит за пределы конечной вычислимости, что приводит к бесконечным вычислениям / гиперкомпьютерам, которые интересны как математические, но не соответствуют выполнимые вычисления.
Вставляйте их параллельно , например, две машины с 3 головками превращаются в машины с 6 головками. Это не говорит нам о том, как компоненты компьютеров взаимодействуют друг с другом.
Чередовать ленты. Одна из проблем этого подхода заключается в том, что неясно, каким может быть каноническое чередование, если оно есть. Более того, чередование «запутает» существующий элемент управления, который, как правило, точно настраивается на конкретную разметку ленты. Таким образом, мы не можем повторно использовать контроль напрямую.
В общем, мы довольно далеко от существенного алгебраического / категориального подхода к вычислительной сложности, и нам потребовалось бы несколько концептуальных достижений, чтобы достичь этого.
источник
Этот ответ об изоморфизмах между формальными языками объединяет алгебраические результаты из теории кодов с понятиями из теории категорий, чтобы исследовать возможные понятия эквивалентности и изоморфизма между формальными языками и классами сложности.
Моя собственная интерпретация этих результатов состоит в том, что точки синхронизации в словах различны для детерминированных и однозначных недетерминированных преобразователей и даже различны для детерминированных прямых и детерминированных обратных преобразователей. Принятие этой точки зрения точек синхронизации позволяет связать эти результаты с визуально выпадающими языками и поднимает вопрос, должны ли они также учитывать простые разделители (например, пробел или запятую) в дополнение к вызовам и возвратам. (Я предполагаю, что разделитель может быть эмулирован комбинированным вызовом return +, но поскольку для этого требуется два символа вместо одного, мне не ясно, достаточно ли этого. Могут также быть видимые языки, которые имеют только разделители, но не символы вызова или возврата.)
источник