Uma categoria de problemas NP-completos?

Faz sentido considerar uma categoria de todos os problemas completos de NP, com morfismos como reduções de politempo entre diferentes instâncias? Alguém já publicou um artigo sobre isso e, em caso afirmativo, onde posso encontrá-lo?

A área que você deseja examinar é chamada "teoria da complexidade implícita". Um punhado de nomes aleatórios e incompletos para o Google são Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca e Kazushige Terui.

A técnica básica é relacionar classes de complexidade a subsistemas de lógica linear (as chamadas "lógicas lineares leves"), com a idéia de que a eliminação de corte para o sistema lógico deve estar completa para a classe de complexidade fornecida (como LOGSPACE, PTIME, etc). Então, através do Curry-Howard, você obtém uma linguagem de programação na qual precisamente os programas da classe são expressáveis. Como você pode esperar da menção da lógica linear, todos esses sistemas dão origem a categorias fechadas monoidais de vários sabores, o que deixa uma caracterização puramente algébrica e independente de máquina de várias classes de complexidade.

Uma das coisas que tornam essa área interessante é que nem a complexidade tradicional nem os métodos lógicos / PL são inteiramente apropriados.

Como as categorias envolvidas geralmente possuem uma estrutura fechada, os métodos combinatórios favorecidos pelos teóricos da complexidade geralmente quebram (uma vez que os programas de ordem superior tendem a resistir às caracterizações combinatórias). Um exemplo típico disso é a falha dos métodos sintáticos em lidar com a equivalência contextual. Da mesma forma, os métodos da semântica também têm problemas, uma vez que muitas vezes são extensos demais (já que tradicionalmente os semanticistas queriam esconder a estrutura interna das funções). O exemplo mais simples que conheço aqui é o fechamento do LOGSPACE sob composição: este é o AFAIK apenas possível devido à recomposição computacional e seletiva e você não pode tratar os problemas como caixas pretas puras.

Você provavelmente também desejará familiarizar-se com a semântica de jogos e com a Geometria da Interação de Girard (e seu precursor, as estruturas de dados concretas de Kahn-Plotkin-Berry) se você se interessar seriamente por essa área - as idéias de representações de passagem de tokens de alto nível. Os cálculos de pedidos usados ​​neste trabalho fornecem muitas intuições para o ICC.

Como apontei o papel central das categorias monoidais neste trabalho, você pode se perguntar sobre as conexões com o TCG de Mulmuley. Infelizmente, não posso ajudá-lo aqui, pois simplesmente não sei o suficiente. Paul-André Melliès pode ser uma boa pessoa para perguntar, no entanto.

É possível categorizar muitas coisas, mas isso não significa necessariamente que sejam categorias interessantes. Portanto, a resposta para "faz sentido" depende de como você quer dizer.

Quanto a prever se seria interessante, assuma alguma definição apropriada de reduções, de modo a formar uma categoria, NPC. As questões teoricamente interessantes da categoria seriam coisas como perguntar se o NPC tem vários limites ou colimits (por exemplo, produtos, coprodutos, pullbacks, pushouts, ...). Portanto, antes de prosseguir com o trabalho de formalizar as coisas, seria bom sentar e pensar sobre o que esses limites significariam e se esse significado seria interessante de se conhecer. Se assumirmos que o NPC tem retrocessos, a capacidade de retroceder duas reduções significa algo especial? Perguntas como estas parecem ser interessantes se quiséssemos descobrir quais são os problemas "atômicos" completos de NP ou como vários problemas completos de NP (ou suas reduções) podem ser combinados;

Algumas perguntas a seguir seriam coisas como: o NPC tem alguma subcategoria interessante? NPC é uma subcategoria de alguma categoria maior e interessante? Já sabemos bastante sobre como os problemas de NP-completos se relacionam com outras classes de problemas, portanto, a resposta presuntiva a essas perguntas é "claro". Mas, para enfatizar, o que considerar essas relações de uma perspectiva teórica da categoria oferece outras perspectivas? Uma coisa que a CT pode oferecer é a questão de saber se existem complementos não triviais entre o NPC e outra categoria. É claro que as adjunções são principalmente interessantes quando as categorias por trás delas são interessantes; por isso, se o NPC não tem muita estrutura especial, o conhecimento sobre as adjunções do NPC não oferece muito.

Quanto a referências particulares, não conheço nenhuma mão secundária, mas os links nos comentários de Sadeq, Ramprasad, Kaveh devem fornecer um ponto de partida.