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

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

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

Например, в 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

Я не претендую на роль эксперта по этим предметам, но я мог бы пролить свет на эту идею.

Сначала рассмотрим теорию категорий. Теория категорий - это исследование математической структуры на очень высоком уровне. Понятие категории очень общее, и множество математических объектов образуют категории. Теория категорий сначала считалась невероятно чистой и абстрактной, но поскольку эти вещи часто бывают в математике, у нее оказалось много применений в прикладных предметах, таких как информатика и даже квантовой механики. Монады оказались полезными в рассуждениях о семантике функциональных программ, которые обычно выражаются денотационно (и, следовательно, не вызывают никакого порядка вычисления, а только результат). Из этого также было осознано, что монада также является очень хорошим шаблоном проектирования для написания функциональных программ, и ее полезность привела к тому, что она была очень заметной в дизайне Haskell (т.е. Обозначение и т.д.). Функторы, Применения, Моноиды, все это несколько позже, как объекты, менее мощные, чем монады, но, следовательно, также более применимы (каламбур не предназначен!).

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

Теория сложности связана с осуществимостью вычисления. Тьюринг и другие показали, что существуют некоторые функции, которые вообще не могут быть вычисляемыми (например, проблема с остановкой, проблема с занятым бобром и т.д.), Но вопрос о том, насколько простой конкретный расчет был в принципе, представляет собой более сложный вопрос в целом. Как вам известно, алгоритмы (которые могут быть представлены как машины Тьюринга) могут быть помещены в классы сложности на основе их асимптотического времени работы. Существует много классов сложности, которые были идентифицированы (см. The Complexity Zoo), но относительно немного известно о структуре этих классов. Известная проблема P = NP показывает, насколько сложно рассуждать о сложности.

Из интуиции о природе классов сложности и о том, как сложно доказать отношения между ними, я бы подумал, что было бы сложно установить категории в классах сложности. Очевидно, что множество машин Тьюринга образует категорию, но множество машин в O (n)? или набор машин в P? Это может быть хорошим направлением исследований для экспертов по сложности, а затем это может и не быть! Лично я не мог сказать, не делая больше работы.

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

Если мы знаем, что определенный тип является моноидом, что мы можем объяснить сложностью работы с ним? Это определение класса из Data.Monoid

class Monoid a where
    mempty  :: a
    mappend :: a -> a -> a
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

Конечно, мы не можем сказать ничего о сложности, потому что все, что мы знаем, это тип, как вы догадались. В документации есть это, чтобы сказать о реализации по умолчанию mconcat в Data.Monoid:

    -- ^ Fold a list using the monoid.
    -- For most types, the default definition for 'mconcat' will be
    -- used, but the function is included in the class definition so
    -- that an optimized version can be provided for specific types.

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

Вы также указываете автоматическое определение параллельных стратегий. Haskell, безусловно, позволяет определить различные стратегии, из которых многие полезные уже находятся в Control.Parallel.Strategies. Например, parList применяет стратегию параллельно каждому элементу списка:

parList :: Strategy a -> Strategy [a]
parList strat []     = ()
parList strat (x:xs) = strat x `par` (parList strat xs)

отсюда можно определить функцию параллельного отображения.

parMap :: Strategy b -> (a -> b) -> [a] -> [b]
parMap strat f xs = map f xs `using` parList strat

using :: a -> Strategy a -> a
using x s = s x `seq` x

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

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

Ответ 2

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

Другая точка зрения - иерархия. Сложные классы формируют категорию poset при включении, и есть некоторые хорошие объекты ограничения, такие как P, PSPACE, NC, AC и т.д.

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

Ответ 3

Быстрый поиск в googling показывает документ:

Безопасная рекурсия Повторение: категориальная семантика и типовые системы для более низкой сложности

Я также помню работы Джапаридзе о полиномиальной арифметике времени, см. http://arxiv.org/abs/0902.2969

Я думаю, вы можете начать оттуда и идти по ссылкам.