Complexité descriptive

La complexité descriptive caractérise les classes de complexité computationnelle par la richesse de la logique nécessaire pour exprimer leurs problèmes, remplaçant les ressources machine telles que le temps et l'espace par la définissabilité logique.

Definition

La complexité descriptive est la branche de la théorie des modèles finis qui classe les problèmes de décision selon la logique capable de les définir sur des structures finies, établissant des correspondances exactes entre les classes de complexité et les langages logiques.

Scope

Ce sujet couvre le théorème de Fagin identifiant NP à la logique existentielle du second ordre, les caractérisations logiques de P, NL et PSPACE par le biais des logiques à point fixe et à clôture transitive, le rôle de l'ordre et du comptage, ainsi que l'utilisation de la théorie des modèles finis pour étudier le pouvoir expressif et aborder les questions relatives aux classes de complexité.

Core questions

• La difficulté computationnelle peut-elle être mesurée par l'expressivité logique plutôt que par les ressources machine ?
• Quelle logique capture NP, et quelle logique capture le temps polynomial ?
• Pourquoi la présence d'un ordre linéaire est-elle importante pour ces caractérisations ?
• Comment les méthodes logiques pourraient-elles influencer la séparation des classes de complexité ?

Key theories

Théorème de Fagin

Une propriété des structures finies est dans NP si et seulement si elle est exprimable en logique existentielle du second ordre, ce résultat fondateur offrant une caractérisation purement logique et indépendante de la machine d'une classe de complexité majeure.

Capture logique de P et PSPACE

Sur les structures ordonnées, le temps polynomial correspond à la logique du premier ordre avec un opérateur de point fixe minimal, et l'espace polynomial à la logique du premier ordre avec un opérateur de point fixe partiel, étendant le programme descriptif à travers la hiérarchie de complexité.

Clinical relevance

La complexité descriptive offre une explication de la traitabilité indépendante de la machine qui clarifie le pouvoir expressif et l'efficacité des langages de requête de bases de données, étant donné que les logiques du premier ordre et à point fixe correspondent à des langages de requête pratiques, et elle propose des outils logiques dont les chercheurs espèrent qu'ils pourront éventuellement aider à séparer les classes de complexité.

History

Fagin a prouvé sa caractérisation de NP en 1974, ouvrant ainsi le domaine. Immerman et Vardi ont indépendamment capturé le temps polynomial par la logique à point fixe sur des structures ordonnées vers 1982, et les travaux d'Immerman sur l'espace non déterministe, y compris la clôture de l'espace non déterministe sous le complément, ont davantage lié la logique à la complexité.

Debates

Existe-t-il une logique capturant le temps polynomial sans ordre ?

La logique à point fixe capture P uniquement lorsqu'un ordre linéaire est disponible. La question de savoir si une logique quelconque capture le temps polynomial sur des structures non ordonnées est un problème ouvert central, car une réponse négative séparerait P de NP et une réponse positive constituerait une avancée majeure.

Key figures

• Ronald Fagin
• Neil Immerman
• Moshe Vardi
• Bruno Courcelle

Seminal works

• immerman1999
• libkin2004

Frequently asked questions

Que signifie capturer une classe de complexité avec une logique ?

Cela signifie que seuls les problèmes de cette classe sont ceux exprimables par des formules de la logique sur des structures finies. Le théorème de Fagin, par exemple, stipule que les problèmes NP sont précisément ceux définissables en logique existentielle du second ordre, de sorte que l'appartenance à la classe devient une question d'expressibilité logique.

Pourquoi la complexité descriptive se soucie-t-elle de l'ordre ?

Plusieurs caractérisations, telles que la logique à point fixe capturant le temps polynomial, ne sont valables que lorsque les structures sont dotées d'un ordre linéaire que la logique peut utiliser. Sans ordre, ces logiques sont plus faibles, et trouver une logique sans ordre pour le temps polynomial est un problème ouvert profond lié à P versus NP.