Étant donné un jeu déterministe à somme partielle et à informations partielles avec seulement un nombre fini d'états, dont les résultats possibles sont [perdre, dessiner, gagner] avec des valeurs [-1,0, + 1] respectivement, quelle est la complexité de l'approximation de la valeur de tels un jeu...
TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd L'entrée Zoo pour TC0TC0\mathsf{TC^0} ne mentionne que la séparation entre la profondeur 2 et 3. Existe-t-il également une référence standard pour le fait que la hiérarchie AC0dACd0\mathsf{AC^0_d} ne...
C'est une question intéressante que j'ai trouvée sur le Web. Étant donné un tableau contenant n nombres (sans aucune information à leur sujet), nous devrions pré-traiter le tableau en temps linéaire afin de pouvoir retourner les k plus petits éléments en temps O (k), quand on nous donne un nombre 1...
Pouvons-nous prouver un résultat de concentration net sur la somme des variables aléatoires exponentielles indépendantes, ie Soit des variables aléatoires indépendantes telles que . Soit . Pouvons-nous prouver des bornes de la forme . Cela suit directement si nous utilisons la forme de variance des...
Cette question est motivée par ce post, pouvez-vous identifier la somme de deux permutations en temps polynomial? et mon intérêt pour les propriétés de calcul des permutations. Une séquence de différences d'une permutation π de nombres 1 , 2 , … n + 1 est formée en trouvant la différence entre tous...
J'ai un très gros automate fini non déterministe et je dois le convertir en DFA. En gros, je veux dire 40 000+ états. Jusqu'à présent, j'ai fait quelques expériences et programmé l'algorithme par défaut qui recherche dans la table (comme décrit ici ), mais même après l'optimisation est assez lente...
Quelles sont les applications concrètes et convaincantes pour estimer le volume de polyèdres convexes du type considéré dans les articles les plus récents sur les méthodes de marche aléatoire? Ces articles sur l'estimation du volume mentionnent l'intégration numérique comme une motivation. Quels...
Cet article prouve que dans un jeu avec des portes et des plaques de pression, il est difficile pour PSPACE de déterminer si l'avatar (du joueur) peut atteindre un emplacement donné. Cela est prouvé par une réduction de TQBF , et la longueur des solutions résultantes dépend exponentiellement du...
Existe-t-il dans une file d'attente de priorité entière qui utilise mots d'espace avec les opérations suivantes, le tout dans le pire des cas et sans accès à l'aléatoire:O(n)O(n)O(n) createEmptyQueueen pour une constante .O(lgcU)O(lgcU)O(lg^c U)ccc insertdans .O(1)O(1)O(1) deleteMinen , où \ delta...
Les automates à états finis résiduels (RFSA, définis dans [DLT02]) sont des NFA qui ont de belles fonctionnalités en commun avec les DFA. En particulier, il y a toujours une RFSA de taille minimale canonique pour chaque langue régulière, et la langue reconnue par chaque état dans la RFSA est un...
Entre chaque niveau de la hiérarchie polynomiale se trouvent différentes classes de complexité, notamment , , et . Faute d'une meilleure terminologie, je les qualifierai, ainsi que d'autres, de classes intermédiaires entre les niveaux et dans la hiérarchie polynomiale. Aux fins de cette question,...
J'ai récemment commencé à lire beaucoup sur la complexité des preuves et j'ai vraiment apprécié ce que j'ai lu. J'aimerais vraiment en savoir plus à ce sujet, mais j'ai du mal à trouver du bon matériel pour les débutants. Quelqu'un pourrait-il recommander des notions de
Assez similaire à ma question précédemment publiée . Cette fois cependant, le graphique n'est pas orienté. Donné Un graphe non orienté sans arêtes multiples ni boucles,GGG Un sommet source ,sss Un sommet cible ttt , Longueur maximale de trajet lll , Je cherche G′G′G' - Un sous-graphe de GGG qui...
J'essaie de comprendre à quelle classe de complexité appartient le problème suivant: Exponentiating Polynomial Root Problem (EPRP) Soit un polynôme avec deg ( p ) ≥ 0 avec des coefficients tirés d'un champ fini G F ( q ) avec q un nombre premier, et r une racine primitive pour ce champ. Déterminez...
Quelles sont les limites connues de la décidabilité de la comparaison du taux de croissance des fonctions de ? Je pense ici à la décidabilité de questions comme "Est-ce que ?" ou "Est-ce que ?".N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg(x+2)⌋x^x \sim 2^{\lfloor x \lg (x+2)...
Je recherche des références bibliographiques pour l'algorithme / problème suivant: je l'ai nommé "BiSelect" ou "t-ary Select" ou "Select in Union of Sorted Arrays", mais je suppose qu'il a été introduit auparavant sous un autre nom? Problème Considérez le problème suivant: Étant donné tableaux...
J'ai lu l'article de Freyd «Catégories algébriquement complètes» dans le célèbre Como90 et j'ai deux questions sur la notion de compacité algébrique qu'il a définie dans cet article. (Si vous n'êtes pas familier avec la définition, la voici: une catégorie est appelée algébriquement compacte si...
Instance: Un graphe non orienté avec deux sommets distincts s ≠ t , et un entier k ≥ 2 .gGGs ≠ ts≠ts\neq tk ≥ 2k≥2k\geq 2 Question: Existe-t-il un chemin dans G , tel que le chemin touche au plus k sommets? (Un sommet est touché par le chemin s'il est sur le chemin ou a un voisin sur le chemin.)s -...
La définition de "poset algébrique" dans les réseaux continus et les domaines , définition I-4.2, dit que, pour tout ,x∈Lx∈Lx \in L l'ensemble doit être un ensemble dirigé, etA(x)=↓x∩K(L)A(x)=↓x∩K(L)A(x) = {\downarrow} x \cap K(L) x=⨆(↓x∩K(L)x=⨆(↓x∩K(L)x = \bigsqcup ({\downarrow} x \cap K(L) . Ici...
Une propriété de graphe est appelée héréditaire si elle se ferme par rapport à la suppression de sommets (c'est-à-dire que tous les sous-graphes induits héritent de la propriété). Une propriété de graphe est appelée additive si elle est fermée par rapport à la prise d'unions disjointes. Il n'est...