Dans l'introduction de cet article Objets partagés éventuellement linéarisables (PODC'10) , les auteurs ont présenté l'énoncé suivant sans références: La linéarisation, cependant, ne peut être atteinte que si et seulement si un consensus peut être trouvé. Ici, la linéarisation est la propriété de...
Soit une famille de sous-ensembles d'éléments d'un univers fini d'objets. Une famille de sous-ensembles d'éléments de , avec , est un - ensemble de frappes de si pour chaque il existe au moins un ensemble tel que .FFFdddUUUHHHkkkUUU1≤k<d1≤k<d1 \le k < d(k,d)(k,d)(k,d)FFFV∈FV∈FV \in FW∈HW∈HW...
Je recherche la complexité de la satisfiabilité d'une formule ou d'une formule où est la formule de la forme: Où est la constante dans et le domaine des variables est également .∃ x 1 , … , x m ∀ y 1 , … , y n , ϕ ϕ ϕ : = ϕ ∧ ϕ | ¬ ϕ | ϕ → ϕ | ψ ψ : = t > t | t∀ y1, … , Yn, ∃ x1, … , Xm,...
LES ÉQUATIONS DIOPHANTINES LINÉAIRES (étant donné les nombres naturels , y a-t-il des nombres naturels x et y tels que a x + b y + c = 0 ?) Sont résolubles en temps polynomial.a , b , cune,b,ca, b, cXXxyyya x + b y+ c = 0uneX+by+c=0ax + by + c = 0 LES ÉQUATIONS DIOPHANTINES QUADRATIQUES ( ) sont...
Il est bien connu que l'existence de fonctions unidirectionnelles est nécessaire et suffisante pour une grande partie de la cryptographie (signatures numériques, générateurs pseudo-aléatoires, cryptage à clé privée, etc.). Ma question est: quelles sont les conséquences théoriques de la complexité...
Les équilibres de Nash ne sont généralement pas calculables. Un équilibre -Nash est un ensemble de stratégies où, compte tenu des stratégies des adversaires, chaque joueur obtient à moins de ϵ du gain maximum possible. Trouver un équilibre ϵ -Nash, étant donné ϵ et un jeu, est P P A D...
Je connais le travail de Shannon avec l'entropie, mais récemment j'ai travaillé sur des structures de données succinctes dans lesquelles l' entropie empirique est souvent utilisée dans le cadre de l'analyse du stockage. Shannon a défini l'entropie des informations produites par une source...
Soit xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} pour i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\} , avec la promesse que x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (où la somme est supérieure à ZZ\mathbb{Z} ). Quelle est alors la complexité de déterminer si x=1x=1x = 1 ?...
Quelles sont certaines des meilleures sources (livres et articles) pour motiver et apprendre la complexité de la communication par elle-même et en relation avec sa relation avec la théorie de la complexité
Quel est l'algorithme d'isomorphisme de graphe non orienté le plus rapide
Nous savons par le théorème de Church que la détermination de la satisfiabilité du premier ordre est indécidable en général, mais il existe plusieurs techniques que nous pouvons utiliser pour déterminer la satisfiabilité du premier ordre. Le plus évident est de rechercher un modèle fini. Cependant,...
Je cherche des références pour le problème suivant: étant donné les entiers et , énumérer tous les graphes planaires non isomorphes sur sommets et la largeur d'arbre . Je m'intéresse à la fois aux résultats théoriques et pratiques, mais surtout aux algorithmes pratiques qu'il est possible de coder...
Cette question est double et est principalement orientée vers la référence: Y a-t-il un endroit où les principales intuitions pour prouver le théorème mineur du graphe sont données, sans trop entrer dans les détails? Je sais que la preuve est longue et difficile, mais il doit sûrement y avoir des...
Soit un graphe qui est l'union disjointe d'une clique et d'un ensemble indépendant, ie ggGG = Kn1+ Kn2¯¯¯¯¯¯¯¯= Kn1+ Jen2.g=Kn1+Kn2¯=Kn1+jen2.G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . La classe de graphes de tous ces graphes est caractérisée par les sous-graphes induits interdits...
Soit GGG et HHH deux graphes connectés rrr réguliers de taille nnn . Soit AAA l'ensemble des permutations PPP tel que PGP−1=HPGP−1=HPGP^{-1}=H . Si G=HG=HG=H alors AAA est l'ensemble des automorphismes de GGG . Quelle est la limite supérieure la plus connue sur la taille de AAA ? Y a-t-il des...
Étant donné un graphe orienté fixe (digramme) , le problème de décision -coloration demande si un digramme d'entrée a un morphisme de . (Un homomorphisme de à est un mappage de à qui préserve les arcs, c'est-à-dire que si est un arc de , alors est un arc de )D G D G D f V ( G ) V ( D ) u v G f ( u...
Le papier SODA de 2 pages de Kalai fournit un algorithme simple et efficace pour la correspondance de motifs avec les soucis (jokers qui correspondent à un caractère). En substance, c'est aussi simple que la convolution. Mais que se passe-t-il si nous recherchons plusieurs modèles sans souci?...
Soit une langue, et définissons par ssi . Je recherche une référence pour:L ⊆ A∗L⊆A∗L \subseteq A^*f L ( x , y ) = 1 x ⋅ y ∈ LFL: A∗× A∗→ { 0 , 1 }fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\}FL( x , y) = 1fL(x,y)=1f_L(x, y) = 1x ⋅ y∈ Lx⋅y∈Lx\cdot y \in L Proposition. est régulier si la...
Pour une langue fixe sur un alphabet A , considérons le problème suivant, que j'appelle L -INTERLEAVING :LLLAAALLL Entrée: deux mots u,v∈A∗u,v∈A∗u, v \in A^* Rendement: s'il existe un entrelacement de et v , qui est en L .uuuvvvLLL Ici, un entrelacement de deux mots et v est un mot w qui peut être...
Existe-t-il un cadre / formalisme qui définit des modèles de calcul basés sur des protéines autres que le modèle d'ADN d'Adleman ou ce travail de Cherry et Qian