Existe uma teoria que combina teoria das categorias / álgebra abstrata e complexidade computacional?

18

A teoria das categorias e a álgebra abstrata lidam com a maneira como as funções podem ser combinadas com outras funções. A teoria da complexidade lida com a dificuldade de calcular uma função. É estranho para mim não ter visto ninguém combinar esses campos de estudo, pois eles parecem pares naturais. Alguém já fez isso antes?


Como um exemplo motivador, vamos dar uma olhada nos monoides. É sabido que, se uma operação é monóide, podemos paralelizar a operação.

Por exemplo, em Haskell, podemos definir trivialmente que a adição é um monóide sobre números inteiros como este:

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

Agora, se quisermos calcular a soma de 0 a 999, poderíamos fazê-lo sequencialmente como:

foldl1' (+) [0..999]

ou poderíamos fazê-lo em paralelo

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

Mas paralelizar esse monóide só faz sentido porque o mappend é executado em tempo constante. E se não fosse esse o caso? As listas, por exemplo, são monoides onde o mappend não executa um tempo inconstante (ou espaço!). Eu estou supondo que é por isso que não há nenhuma função mconcat paralela padrão no Haskell. A melhor implementação depende da complexidade do monóide.


Parece que deve haver uma maneira conveniente de descrever as diferenças entre esses dois monóides. Deveríamos, então, poder anotar nosso código com essas diferenças e fazer com que os programas escolham automaticamente os melhores algoritmos para usar, dependendo da complexidade de um monóide.

Mike Izbicki
fonte
1
O tipo Inteiro em Haskell é um número inteiro de precisão múltipla, e a complexidade do tempo de adição neles depende naturalmente do comprimento dos números inteiros de entrada; portanto, é enganoso dizer que o mappend na sua instância Monoid para Número Inteiro é executado em tempo constante.
Tsuyoshi Ito
@TsuyoshiIto Você está certo, eu pretendia usar o Int. Fixo.
Mike Izbicki 03/08/2012
Você já viu essa pergunta ?
Kaveh
@ Kaveh eu não tinha, obrigado pelo ponteiro. De uma leitura rápida, parece que ninguém fez nenhum trabalho teórico de categoria nas próprias classes de complexidade (e há algum debate sobre o que isso pode significar ou se é um objetivo que vale a pena). Então, eu acho que isso praticamente responde à primeira parte da minha pergunta e deixa qualquer interação entre álgebra e complexidade.
Mike Izbicki
Há muita interação entre álgebra e teoria da complexidade. Existem até livros intitulados "Algebraic Complexity Theory" que usam e aplicam conceitos e técnicas algébricas à complexidade. E também existem trabalhos extensos que aplicam a teoria da complexidade à álgebra. Você precisa ser mais específico para obter uma resposta.
Kaveh

Respostas:

12

[Complexidade computacional e teoria das categorias] parecem pares naturais.

Dado o destaque da complexidade computacional como um campo de pesquisa, se eles fossem companheiros naturais, talvez alguém já tivesse trazido a conexão?

Especulação selvagem. Deixe-me entreter o leitor com pensamentos sobre o porquê de uma renderização categórica da complexidade computacional ser difícil. Indiscutivelmente, o cluster de conceitos-chave na teoria das categorias está centrado em construções / propriedades universais (com o aparato associado de functores, transformações naturais, complementos e assim por diante). Se pudermos mostrar que uma construção matemática tem uma propriedade universal, isso fornece muitas informações. Portanto, se quiséssemos uma abordagem categórica da complexidade computacional, precisaríamos encontrar uma categoria conveniente e exibir como os conceitos-chave da teoria da complexidade (por exemplo, LOGSPACE ou dureza NP) podem ser dados por construções universais usando essa categoria. Isso ainda não foi feito, e acho que é porque é um problema realmente difícil.

T=T1T2T3TEu,1 . Em vez disso, construímos TMs especificando seus dois componentes separadamente: o controle (um FSM) e a fita. Nem o controle nem a fita possuem boas álgebras.

Vamos ver as fitas primeiro. Existem algumas maneiras naturais de compor fitas, nenhuma das quais parece funcionar para uma descrição composicional das MTs.

  • Cole-os juntos como adição ordinal. Esta não é a noção correta, porque as fitas são infinitas e, juntando-as como adição ordinal, obtemos um objeto infinito duplo que vai além da computabilidade finita, levando a computação / hipercomputação infinita, que são interessantes como matemáticas, mas não correspondem a computação viável.

  • Cole-os em paralelo , por exemplo, duas máquinas de 3 cabeças se transformam em uma máquina de 6 cabeças. Isso não nos diz como as máquinas componentes interagem umas com as outras.

  • Entrelaçar fitas. Um problema com essa abordagem é que não está claro qual poderia ser a intercalação canônica, se houver. Além disso, a intercalação 'confundirá' o controle existente, que tende a ser afinado para um layout de fita específico. Portanto, não podemos reutilizar o controle diretamente.

π

Em suma, estamos muito distantes de um tratamento algébrico / categórico substancial da complexidade computacional e precisaríamos de vários avanços conceituais para chegar lá.


λπλπαλπ

Martin Berger
fonte
Eu diria que a composição das máquinas de Turing é bastante clara quando você as pensa como programas de computador abstratos. A maneira natural de compor programas é chamar um como subprograma de outro. De um modo mais geral, cada programa é computável em uma função finita de tempo e espaço, que aceita certas entradas formatadas e produz outra string formatada, que pode ser alimentada em outra função. É possível que algumas entradas de lixo resultem em saídas de lixo ou que alguma função não seja executada no tempo e espaço alocados; nesse caso, o programa inteiro trava.
Anton Fetisov 30/07/2018
Obviamente, nem todos os programas são composíveis dessa maneira, o que naturalmente nos leva a uma categoria de TMs. Também é provável que se deva abandonar a noção de uma TM ilimitada no tempo-espaço, o que não é praticamente possível de qualquer maneira. Existe alguma noção publicada que captura essa estrutura?
Anton Fetisov 30/07/19
@AntonFetisov Você já tentou escrever os detalhes? Não é bonito.
Martin Berger
2

Esta resposta sobre isomorfismos entre linguagens formais combina resultados algébricos da teoria dos códigos com noções da teoria das categorias para investigar possíveis noções de equivalência e isomorfismo entre linguagens formais e classes de complexidade.

Minha própria interpretação desses resultados é que os pontos de sincronização nas palavras são diferentes para transdutores determinísticos e não-ambíguos não-determinísticos e até diferentes entre transdutores determinísticos para a frente e determinísticos para trás. Tomar essa perspectiva dos pontos de sincronização permite conectar esses resultados a linguagens visíveis de empilhamento e levanta a questão de saber se eles também devem considerar separadores simples (como um espaço ou vírgula) além de chamadas e retornos. (Meu palpite é que um separador pode ser emulado por uma chamada de retorno + combinada, mas como esses requerem dois símbolos em vez de um, não está claro se isso é suficiente. Também pode haver idiomas visíveis que possuem apenas separadores, mas não chamar ou retornar símbolos.)

Thomas Klimpel
fonte
Eu criei este wiki da comunidade, porque ele tem links para minha própria resposta à minha própria pergunta, o que certamente não é ótimo. Eu estava "limpando" meus favoritos e apenas escrever essa resposta curta era a maneira mais fácil de prosseguir.
21815 Thomas Klimpel