P et complexité descriptive

10

Dans le Complexity Zoo, il est dit [ 1 ] que, dans la complexité descriptive, P peut être défini par trois types de formules différents, FO(LFP) qui est aussi FO(nO(1)) , et aussi comme SO(HORN) .

Cependant, il y a quelques exceptions, par exemple, Evenness ne peuvent pas être exprimées par FP (FP a la même puissance expressive avec LFP). Connectivity et 2−colourability ne sont pas définissables par la logique du premier ordre. Certains problèmes ne peuvent même pas être axiomatisés avec un nombre fini de variables telles que Evenness ,Perfect Matching ,Hamiltonicity .

Immerman a proposé que la logique à point fixe + le comptage (FPC) soit une logique possible pour capturer P.

Cependant, Cai Furer, Immerman a montré qu'il existe des propriétés de graphe en temps polynomial qui ne sont pas exprimables en FPC [ 2 ]. Le problème de la résolution d'équations linéaires sur le champ à deux éléments n'est pas définissable en logique infinitaire avec comptage [ 3 ]. Vous pouvez vous référer à [ 4 ] pour plus de détails.

Alors, quelle structure logique peut capturer P en général? La réponse positive est qu'une classe de structures finies ordonnées est définissable en logique à point fixe minimum si, et seulement si, elle est décidable en P par Immerman [ 5 ] et Vardi [ 6 ]. Et dans le cas non ordonné? Pouvez-vous montrer plus de contre-exemples de la déclaration dans le zoo de la complexité?

lo.logic polynomial-time descriptive-complexity Rupei Xu
la source
2
Voici un tutoriel donnant un aperçu des résultats sur cette question particulière: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf
Denis
@Denis Merci Denis! Ce tutoriel contient plus de structures logiques pour P. Traditionnellement, lorsque nous parlons d'un problème résolvable en temps polynomial, nous pensons qu'il est "facile". Cependant, les structures logiques de P semblent si compliquées, et il y a encore beaucoup de cas inconnus et de problèmes ouverts.
Rupei Xu
1
Oui, il semblerait que l'ensemble des problèmes «faciles» (c'est-à-dire P) ne soit pas si bien structuré et soit difficile à caractériser avec quelque chose comme «les problèmes faciles sont ceux qui peuvent être obtenus à partir des problèmes de base A, B, C, combinés de façon X, Y ". Il y a toujours des problèmes plus faciles qui sont d'un autre type et qui nécessitent des algorithmes polynomiaux intelligents avec de nouvelles idées.
Denis

Réponses:

2

Martin Grohe a fait des progrès substantiels sur cette question récemment. Il donne une logique capturant le temps polynomial sur des classes de graphes intégrables dans une surface fixe: https://dl.acm.org/citation.cfm?doid=2371656.2371662 Edit: le cas général semble non résolu (mais je ne le suis en aucun cas un expert en la matière).

Hermann Gruber
la source
Oui. Il y a beaucoup de résultats algorithmiques de méta-théorèmes (comme le célèbre théorème de Courcelle) qui peuvent capturer les cas faciles, le lien suivant est un bon papier d'enquête. people.cs.umass.edu/~immerman/pub/… Cependant, ces résultats ont également la restriction pour les structures de graphique sur lesquelles le problème s'exécute, telles que l'arbre, la largeur d'arbre limitée, les graphiques planaires, les graphiques fermés mineurs, etc. jusqu'à présent, aucune structure logique complète ne peut capturer P dans des graphiques généraux sans ordre.
Rupei Xu
Je suppose que le travail de Grohe est assez spécial car dans ce cas, la logique épuise tout P sur une classe de graphes remarquablement grande, c'est-à-dire qu'il n'y a pas de contre-exemples. Si j'ai bien compris, être exhaustif est la partie difficile. Les résultats MSO que vous mentionnez ne semblent pas avoir cette fonctionnalité. Mais mon expertise à cet égard est très limitée, je peux me tromper ici.
Hermann Gruber