Une catégorie de problèmes NP-complets?

Est-il judicieux de considérer une catégorie de tous les problèmes NP-complets, avec des morphismes comme des réductions de poly-temps entre différentes instances? Quelqu'un a-t-il déjà publié un article à ce sujet, et si oui, où puis-je le trouver?

Le domaine que vous souhaitez examiner est appelé "théorie de la complexité implicite". Une poignée de noms aléatoires et incomplets pour Google sont Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca et Kazushige Terui.

La technique de base consiste à relier les classes de complexité aux sous-systèmes de logique linéaire (les soi-disant "logiques linéaires légères"), avec l'idée que l'élimination des coupures pour le système logique devrait être complète pour la classe de complexité donnée (comme LOGSPACE, PTIME, etc.). Ensuite, via Curry-Howard, vous obtenez un langage de programmation dans lequel précisément les programmes de la classe donnée sont exprimables. Comme vous pouvez vous attendre de la mention de la logique linéaire, tous ces systèmes donnent alors naissance à des catégories fermées monoïdales de diverses saveurs, ce qui vous laisse une caractérisation purement algébrique et indépendante de la machine de différentes classes de complexité.

L'une des choses qui rendent ce domaine intéressant est que ni la complexité traditionnelle ni les méthodes logiques / PL ne sont tout à fait appropriées.

Comme les catégories impliquées ont généralement une structure fermée, les méthodes combinatoires privilégiées par les théoriciens de la complexité tombent souvent en panne (car les programmes d'ordre supérieur ont tendance à résister aux caractérisations combinatoires). Un exemple typique de ceci est l'échec des méthodes syntaxiques pour gérer l'équivalence contextuelle. De même, les méthodes de la sémantique ont aussi du mal, car elles sont souvent trop extensionnelles (car traditionnellement les sémantistes ont voulu cacher la structure interne des fonctions). L'exemple le plus simple que je connaisse ici est la fermeture de LOGSPACE en cours de composition: c'est l'AFAIK uniquement possible en raison de la queue d'aronde et du recalcul sélectif, et vous ne pouvez pas traiter les problèmes comme des boîtes noires pures.

Vous voudrez probablement également vous familiariser avec la sémantique des jeux et la géométrie de l'interaction de Girard (et leur précurseur, les structures de données concrètes de Kahn-Plotkin-Berry) si vous vous lancez sérieusement dans ce domaine - les idées de représentations par passage de jetons de les calculs d'ordres utilisés dans ce travail fournissent beaucoup d'intuitions pour ICC.

Puisque j'ai souligné le rôle central des catégories monoïdales dans ce travail, vous pourriez raisonnablement vous interroger sur les connexions avec le GCT de Mulmuley. Malheureusement, je ne peux pas vous aider ici, car je n'en sais pas assez. Mais Paul-André Melliès est peut-être une bonne personne à poser.

Il est possible de classer beaucoup de choses, mais cela ne signifie pas nécessairement que ce sont des catégories intéressantes. La réponse à "est-ce que cela a du sens" dépend donc de la façon dont vous entendez.

Quant à prédire si ce serait intéressant, supposons une définition appropriée des réductions de telle sorte qu'elle forme une catégorie, NPC. Les questions théoriquement intéressantes seraient des choses comme demander si le PNJ a différentes limites ou colimites (par exemple, produits, coproduits, retraits, pushouts, ...). Donc, avant d'entreprendre le travail de formalisation des choses, il serait bon de s'asseoir et de réfléchir à ce que ces co / limites signifieraient et si cette signification serait intéressante à connaître. Si nous supposons que le PNJ a des retraits, la possibilité de prendre le recul de deux réductions signifie-t-elle quelque chose de spécial? Des questions comme celles-ci semblent être intéressantes si nous voulions comprendre quels sont les problèmes NP-complets "atomiques", ou comment combiner plusieurs problèmes NP-complets (ou leurs réductions);

Certaines questions de suivi seraient des choses comme: le PNJ a-t-il des sous-catégories intéressantes? NPC est-il une sous-catégorie de grandes catégories intéressantes? Nous savons déjà beaucoup de choses sur la façon dont les problèmes NP-complets sont liés à d'autres classes de problèmes, donc la réponse présumée à ces questions est "bien sûr". Mais pour mettre un point plus fin là-dessus, qu'est-ce que la considération de ces relations d'un point de vue théorique de catégorie offre que d'autres perspectives ne font pas? Une chose que CT peut offrir est la question de savoir s'il existe des adjonctions non triviales entre NPC et une autre catégorie. Bien sûr, les adjonctions sont principalement intéressantes lorsque les catégories derrière elles sont elles-mêmes intéressantes, donc si NPC n'a pas beaucoup de structure spéciale, connaître les adjonctions NPC n'offrira pas vraiment grand-chose.

En ce qui concerne les références particulières, je n'en connais aucune, mais les liens dans les commentaires de Sadeq, Ramprasad, Kaveh devraient fournir un point de départ.