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

28

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?

Paul Allen Grubbs
la source
1
Je ne sais pas pourquoi vous voulez la catégorie des seuls problèmes NP-complets, mais la catégorie de tous les problèmes de décision avec une notion fixe de réductions (telles que les réductions de plusieurs à un temps polynomial), car les morphismes semblent un objet raisonnable à considérer. Je ne connais pas du tout la théorie des catégories et je ne peux pas deviner si elle est intéressante ou non.
Tsuyoshi Ito
1
Je ne suis pas sûr que cela aide, mais je vais essayer: sur les isomorphismes et la densité de NP et d'autres ensembles complets . Voir aussi la version du journal . Voir aussi l'article de Mahaney .
MS Dousti
2
Je voulais juste développer le commentaire de Sadeq. Isomorphisme entre problèmes COMPLETES a été étudié et beaucoup de travail a été fait pour prouver / réfutant la conjecture Berman-Hartmanis (qui stipule que tous les N P problème -complete sont « isomorphe » en temps polynomial plusieurs-une réduction) . Voici une étude de Manindra Agrawal sur la conjecture d'isomorphisme ( cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf ). NPNP
Ramprasad
1
@Tsuyoshi: même la catégorie des problèmes de PNJ avec les réductions de Karp pourrait être intéressante - si nous comprenions vraiment même cette catégorie, nous aurions une bien meilleure compréhension de la complexité en général (car cela impliquerait probablement une bien meilleure compréhension de Karp réductions, donc de temps polynomial). OTOH, je ne suis pas sûr que le voir comme une catégorie fournira une voie à suivre pour faciliter la compréhension. J'ai réfléchi à cette question dans le passé, et j'ai cherché des références qui voient la complexité de cette façon, et je n'en ai pas trouvé. J'espère que quelqu'un le fera!
Joshua Grochow du
3
J'appuie Joshua. Ce qui est important, c'est de ne pas pouvoir définir une catégorie, ce qui est important, c'est d'y trouver une structure catégorielle intéressante. Il existe des structures intéressantes dans le cas de la calculabilité, mais pour la complexité, je ne sais pas. Andrej devrait mieux connaître et, espérons-le, vérifiera cette question.
Kaveh

Réponses:

21

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.

Neel Krishnaswami
la source
16

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.

wren romano
la source