La complexité descriptive classe les problèmes en fonction de la difficulté à exprimer le problème dans un certain formalisme logique.
Le théorème d'Immerman-Vardi stipule que PTIME (ou P) est précisément la classe de langages pouvant être décrite par une phrase de la logique du premier ordre avec un opérateur à point fixe, sur la classe des structures ordonnées. L'opérateur de point fixe peut être soit le point le moins fixe...
Le titre en dit plus ou moins, mais je suppose que je pourrais ajouter un peu de contexte et quelques exemples spécifiques qui m'intéressent. Les théoriciens de la complexité descriptive, tels que Immerman et Fagin, ont caractérisé la plupart des classes de complexité les plus connues à l'aide de...
Il semble connu que pour trouver une réponse à une requête sur une base de données relationnelle D , il faut du temps | D | | Q | , et on ne peut pas se débarrasser de l'exposant | Q | .QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Comme peut être très volumineux, nous nous demandons pourquoi les bases de...
Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...
Le papier Lauri Hella et José María Turull-Torres, Requêtes informatiques avec des logiques d'ordre supérieur , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 propose une logique VO, une logique d'ordre variable. Cela permet de quantifier les commandes sur les variables. VO est assez...
CMSOL est la logique de deuxième ordre monadique, c'est-à-dire une logique de graphiques où le domaine est l'ensemble des sommets et des arêtes, il y a des prédicats pour la contiguïté des sommets et les incidences des arêtes et des sommets, il y a une quantification sur les arêtes, les sommets,...
Soit une permutation. Notez que tandis que agit sur un domaine infini, sa description peut être finie. Par description , je veux dire un programme qui décrit les fonctionnalités de . (Comme dans la complexité de Kolmogorov.) Voir les explications ci-dessous. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi...
Dans cette question , il a été mentionné qu'il existe des versions de complexité descriptive du théorème de Rice. J'ai trouvé une preuve du théorème suivant: Étant donné une classe de complexité C , les propriétés non triviales des langages en C ne peuvent pas être calculées en C J'avais déjà posté...
Contexte: Nous considérons uniquement les digraphes. Soit CYCLE le langage des graphes avec un cycle; c'est un problème NL-complet. Soit HASEDGE le langage des graphiques avec au moins un bord. Ensuite, trivialement, n'est plus NL-hard, tandis que reste.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup...
Il est bien connu que certaines catégories de NP -Problèmes Ont dichotomie théorèmes, qui garantit que toutes les tâches de la classe est soit NP -complete ou est en P . Le résultat le plus connu est le théorème de dichotomie de Schaefer , ainsi qu'un certain nombre de généralisations. Je crois...
Dans le Complexity Zoo, il est dit [ 1 ] que, dans la complexité descriptive, PPP peut être défini par trois types de formules différents, FO(LFP)FO(LFP)FO(LFP) qui est aussi FO(nO(1))FO(nO(1))FO(n^{O(1)}) , et aussi comme SO(HORN)SO(HORN)SO(HORN) . Cependant, il y a quelques exceptions, par...
Ma question concerne la théorie des modèles finis / la complexité descriptive, donc signifiera "premier ordre sur des mots binaires finis, en utilisant des prédicats Rs et un prédicat unaire P vrai sur la position du 1 dans le mot".FO ( R )FO(R)FO(R) Je voudrais savoir, existe-t-il une...
J'essaie de comprendre le document sur les systèmes de preuve p-optimaux et la logique pour PTIME . Il y a une notion appelée systèmes de preuve dans le papier et je ne comprends pas l'intution: ... Nous identifions des problèmes avec des sous-ensembles de Q dans Σ ∗ .Σ={0,1}Σ={0,1}\Sigma =...
Pour mieux comprendre un article, j'essaie d'obtenir une brève compréhension de la logique des points les moins fixes. Il y a quelques points où je suis coincé. Si est un graphique etG = ( V, E)G=(V,E)G = (V,E) Φ ( P) = { ( a , b ) ∣ G ⊨ E( a , b ) ∨ P( a , b ) ∨ ∃ z( E( a , z) ∧ P( z, b ) )...
Fermé. Cette question est hors sujet . Il n'accepte pas actuellement les réponses. Vous souhaitez améliorer cette question? Mettez à jour la question afin qu'elle soit sur le sujet pour l'échange théorique de pile informatique. Fermé il y a 7 ans . Comment exprimer " " comme une formule de premier...