Complexité descriptive -Descriptive Complexity
Descriptive Complexity est un livre sur la logique mathématique et la théorie de la complexité computationnelle de Neil Immerman . Il concerne la théorie de la complexité descriptive , un domaine dans lequel l'expressibilité des propriétés mathématiques utilisant différents types de logique est équivalente à leur calculabilité dans différents types de modèles de calcul limités aux ressources. Il a été publié en 1999 par Springer-Verlag dans leur série de livres Graduate Texts in Computer Science.
Les sujets
Le livre comprend 15 chapitres, regroupés en gros en cinq chapitres sur la logique du premier ordre , trois sur la logique du second ordre et sept chapitres indépendants sur des sujets avancés.
Les deux premiers chapitres fournissent des informations de base sur la logique du premier ordre (y compris l' arithmétique du premier ordre , le prédicat BIT et la notion de requête du premier ordre) et la théorie de la complexité (y compris les langages formels , les classes de complexité liées aux ressources et les problèmes complets ). Le chapitre trois commence la connexion entre la logique et la complexité, avec une preuve que les langages reconnaissables du premier ordre peuvent être reconnus dans l' espace logarithmique , et la construction de langages complets pour l'espace logarithmique, l'espace logarithmique non déterministe et le temps polynomial . Le quatrième chapitre concerne les définitions inductives, les opérateurs en virgule fixe et la caractérisation du temps polynomial en termes de logique du premier ordre avec l'opérateur le moins fixe. La partie du livre sur les sujets de premier ordre se termine par un chapitre sur les caractérisations logiques des limites de ressources pour les machines à accès aléatoire parallèles et la complexité des circuits .
Le chapitre six présente les jeux Ehrenfeucht – Fraïssé , un outil clé pour prouver l'inexpressibilité logique, et le chapitre sept introduit la logique du second ordre. Il inclut le théorème de Fagin caractérisant le temps polynomial non déterministe en termes de logique existentielle du second ordre, le théorème de Cook-Levin sur l'existence de problèmes NP-complets et des extensions de ces résultats à la hiérarchie polynomiale . Le chapitre huit utilise des jeux pour prouver l'inexprimabilité de certaines langues en logique du second ordre.
Le chapitre neuf concerne la complémentation des langages et l' opérateur de fermeture transitive , y compris le théorème d'Immerman – Szelepcsényi selon lequel l'espace logarithmique non déterministe est fermé sous complémentation. Le chapitre dix fournit des problèmes complets et une caractérisation logique du second ordre de l' espace polynomial . Le chapitre onze concerne l' uniformité dans la complexité des circuits (la distinction entre l'existence de circuits pour résoudre un problème et leur constructibilité algorithmique), et le chapitre douze concerne le rôle de l'ordre et du comptage des prédicats dans les caractérisations logiques des classes de complexité. Le chapitre treize utilise le lemme de commutation pour les limites inférieures, et le chapitre quatorze concerne les applications aux bases de données et la vérification de modèle . Un dernier chapitre présente les sujets qui nécessitent encore des recherches dans ce domaine.
Public et accueil
Le livre se veut avant tout une référence aux chercheurs dans ce domaine, mais il pourrait également être utilisé comme base d'un cours de troisième cycle et est équipé d'exercices à cet effet. Bien qu'il prétende être autonome, le critique W. Klonowski écrit que ses lecteurs doivent déjà comprendre à la fois la complexité classique et les bases de la logique mathématique.
Le critique Anuj Dawar écrit qu'une partie des promesses précoces de la complexité descriptive a été atténuée par son incapacité à apporter des outils logiques pour porter sur les problèmes fondamentaux de la théorie de la complexité, et par la nécessité d'ajouter des ajouts de type calcul aux langages logiques afin d'utiliser eux pour caractériser le calcul. Néanmoins, écrit-il, le livre est utile comme moyen d'initier les chercheurs à cette ligne de recherche et à une manière moins explorée d'aborder la complexité informatique.
