Uma categoria de problemas NP-completos?

28

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?

Paul Allen Grubbs
fonte
1
Não sei por que você deseja a categoria apenas de problemas NP completos, mas a categoria de todos os problemas de decisão com alguma noção fixa de reduções (como reduções polinomiais de muitas e uma), pois os morfismos parecem um objeto razoável a ser considerado. Não conheço a teoria das categorias e não consigo adivinhar se é interessante ou não.
Tsuyoshi Ito
1
Não tenho certeza se isso ajuda, mas vou tentar: isomorfismos e densidade de NP e outros conjuntos completos . Veja também a versão do diário . Veja também o artigo de Mahaney .
MS Dousti 17/11/2010
2
Só queria elaborar o comentário de Sadeq. Isomorfismo entre problemas -Complete tem sido estudada e uma grande quantidade de trabalho tem sido feito no sentido de provar / refutar a conjectura Berman-Hartmanis (que afirma que todos os N P problema -completo são "isomórfico" sob tempo polinomial muitos-um reduções) . Aqui está uma pesquisa de Manindra Agrawal sobre a conjectura de isomorfismo ( cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf ). NPNP
Ramprasad #
1
@Tsuyoshi: até a categoria de problemas de NPCs com reduções de Karp poderia ser potencialmente interessante - se realmente entendêssemos mesmo essa categoria, teríamos uma compreensão muito melhor da complexidade em geral (já que provavelmente implicaria uma compreensão muito melhor de Karp reduções, portanto do tempo polinomial). OTOH, não tenho certeza de que vê-lo como uma categoria fornecerá um caminho a seguir para ajudar no entendimento. Eu pensei sobre esse problema alguns no passado e procurei referências que visualizassem a complexidade dessa maneira e não encontrassem nenhuma. Espero que alguém faça!
Joshua Grochow
3
Eu segundo Joshua. O importante é não poder definir uma categoria, o importante é encontrar nela uma estrutura categórica interessante. Existem estruturas interessantes no caso da computabilidade, mas por complexidade não sei. Andrej deve conhecer melhor e, esperançosamente, verificar esta questão.
Kaveh

Respostas:

21

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.

Neel Krishnaswami
fonte
16

É 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.

wren romano
fonte