Есть ли теория, которая сочетает в себе теорию категорий / абстрактную алгебру и вычислительную сложность?
Теория категорий и абстрактная алгебра имеют дело со способом, которым функции могут быть объединены с другими функциями. Теория сложности имеет дело с тем, насколько сложно вычислить функцию. Мне странно, что я не видел, чтобы кто-нибудь совмещал эти области изучения, так как они кажутся такими естественными парами. Кто-нибудь делал это раньше?
В качестве мотивирующего примера давайте посмотрим на моноиды. Хорошо известно, что если операция является моноидом, то мы можем распараллелить операцию.
Например, в 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. Наилучшая реализация зависит от сложности моноида.
Кажется, должен быть удобный способ описать различия между этими двумя моноидами. Затем мы должны иметь возможность комментировать наш код с этими различиями и иметь программы автоматически выбирать лучшие алгоритмы для использования в зависимости от сложности моноида.
3 ответа
Я не претендую на звание эксперта по этим вопросам, но я мог бы пролить свет на эту идею.
Давайте сначала рассмотрим теорию категорий. Теория категорий - это изучение математической структуры на очень высоком уровне. Понятие категории является очень общим, и множество математических объектов образуют категории. Теория категорий вначале считалась невероятно чистой и абстрактной, но поскольку эти вещи часто встречаются в математике, оказалось, что она имеет множество применений в прикладных предметах, таких как информатика и даже квантовая механика. Оказалось, что монады очень полезны для рассуждения о семантике функциональных программ, которые обычно выражаются денотационно (и, следовательно, не навязывают какой-либо порядок вычислений, а только результат). Из этого также стало понятно, что монада также является очень хорошим шаблоном проектирования для написания функциональных программ, и ее полезность привела к тому, что она стала очень заметной в дизайне Haskell (то есть нотации do и т. Д.). Функторы, Аппликативы, Моноиды - все они несколько позже стали объектами, менее мощными, чем монады, но, следовательно, также более аппликативными (без каламбура!).
Тем не менее, теория категорий сама по себе изучает такие структуры гораздо более общим образом, что оказалось актуальным во многих областях математики (и физики и т. Д.). Как не специалист, не сразу понятно, насколько это может быть связано с теорией сложности, но давайте попробуем.
Теория сложности связана с осуществимостью вычислений. Тьюринг и другие показали, что есть некоторые функции, которые вообще не поддаются вычислению (например, проблема остановки, проблема занятого бобра и т. Д.), Но вопрос о том, насколько легко в принципе было выполнить конкретное вычисление, является более сложным вопросом в целом. Как вы, вероятно, знаете, алгоритмы (которые могут быть представлены как машины Тьюринга) могут быть помещены в классы сложности на основе их асимптотического времени выполнения. Существует очень много классов сложности, которые были идентифицированы (см . Зоопарк сложности), но сравнительно мало известно о структуре этих классов. Знаменитая проблема P = NP показывает, насколько сложно рассуждать о сложности.
Исходя из интуиции о природе классов сложности и о том, как трудно доказать взаимосвязь между ними, я бы подумал, что было бы сложно установить категории внутри классов сложности. Очевидно, что множество машин Тьюринга образует категорию, но множество машин в O(n)? или множество машин в P? Это может быть хорошим научным направлением для специалистов по сложности, а может и нет! Лично я не мог сказать без намного большего количества работы.
Теперь давайте рассмотрим ваш пример сложности внутри Monoid и стратегии распараллеливания. Если кажется, что этот второй раздел имеет мало общего с первым, то это потому, что я думаю, что это очень разные понятия. Во-первых, это математика категорий и сложности, во-вторых, есть особенности распараллеливания алгоритмов в рамках определенных шаблонов проектирования.
Если мы знаем, что определенный тип является моноидом, что мы можем рассуждать о сложности работы с ним? Это определение класса из 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
Обратите внимание, что это позволяет разделить реализацию и распараллеливание. Я не думаю, что такого рода понятие может быть легко автоматизировано, особенно из аннотаций, описывающих сложность отдельных алгоритмов.
Таким образом, возможно, что теория категорий может быть полезным инструментом для будущих исследований сложности. Однако я не думаю, что это может привести к автоматической генерации стратегий распараллеливания.
На поверхностном уровне теоретики сложности уже занимаются вопросами теории категорий, они просто формулируют это на своем родном языке. Например, класс сложности NP- это категория, где объекты - это языки NP, а морфизмы - сокращения за полиномиальное время. Тогда полная задача является начальным объектом в этой категории, и все NP-полные задачи изоморфны. Как и в ответе Вика, не очень разумно рассматривать машины Тьюринга как объекты. Это происходит главным образом из-за того, насколько гибкими могут быть машины Тьюринга (это много разных моделей машин Тьюринга с совершенно разными временными и пространственными сложностями для одних и тех же задач). Но тезисная идея теории категорий о том, что основной интерес к категории заключается в морфизмах, говорит нам, что морфизмы должны быть алгоритмами.
Другое мнение - это иерархии. Классы сложности формируют категорию poset при включении, и есть несколько хороших предельных объектов, таких как P, PSPACE, NC, AC и т. Д.
Конечно, неясно, как категориальная перспектива помогает нам доказать теоремы в теории сложности, и будет ли решение проблем с помощью теории категорий проще, чем решение исходных задач. Например, я бы рассматривал существование нетривиального функтора из категории poset классов сложности, скажем, для категории групп, как результат дикого преобразования. Было бы возможно разделить классы сложности, что в этой области само по себе непомерно сложно.
Быстрый поиск в Google показывает бумагу:
Я также помню работы Джапаридзе по арифметике за полиномиальное время, см. http://arxiv.org/abs/0902.2969
Я думаю, что вы можете начать оттуда и идти по ссылкам.