La coloration à 3 arêtes des graphiques cubiques est complète. Le théorème à quatre couleurs équivaut à «Chaque graphique cubique sans pont plan est colorable sur 3 bords».NPNPNP Quelle est la complexité de la coloration à 3 arêtes des graphiques planaires cubiques? De plus, il est conjecturé que...
Cette question peut être posée soit dans le cadre de la complexité des circuits des circuits booléens, soit dans le cadre de la théorie de la complexité algébrique, soit probablement dans de nombreux autres contextes. Il est facile de montrer, en comptant les arguments, qu'il existe des fonctions...
Soit et y deux nombres binaires à n bits et z = x ⋅ y le nombre binaire (longueur 2 n ) du produit de x et y . Nous voulons calculer le bit le plus siginifcant z 2 n - 1 du produit z = z 2 n - 1 … z 0 .Xxxyyynnnz= x ⋅ y z=x⋅y z = x \cdot y\ 2 n2n2nXxxyyyz2 n - 1z2n−1z_{2n-1}z= z2 n - 1…...
Je m'intéresse à la génération de nombres pseudo-aléatoires pour la cryptographie. Outre le chapitre 5 de Menezes / Oorschot / Vanstone ; Chapitre 8 de Stinson ; et le chapitre 3 de Goldreich , où pourrais-je trouver plus? Je m'intéresse aux principes généraux de conception des PRNG (propriétés...
Ma question est d'ordre général: comment commencer à penser en termes de conception d'algorithmes et de complexité? Je vais suivre un cours d'études supérieures en conception d'algorithmes. Je m'y étais inscrit plus tôt mais je l'ai abandonné plus tard parce que je ne pouvais pas suivre. Je dois...
Nous considérons souvent les classes de complexité où nous sommes limités dans la quantité d'espace que notre machine de Turing peut utiliser, par exemple: ou NSPACE ( f ( n ) ) . Il semble qu'au début de la théorie de la complexité, il y eut beaucoup de succès avec ces classes telles que le...
J'ai récemment découvert une borne inférieure quadratique sur la complexité d'un problème dans le modèle d'arbre de décision, et je me demande si ce résultat pourrait être partiellement généralisé au modèle de machine à accès aléatoire. Par partiellement , je veux dire une généralisation aux...
En lisant l'article " Une théorie applicative pour la FPH ", vous pouvez rencontrer le passage suivant: Compte tenu des théories qui caractérisent les classes de complexité informatique, il existe trois approches différentes: dans l'un, les fonctions qui peuvent être définies dans la théorie sont...
Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction...
Un ensemble de frappe d'une famille est un sous-ensemble de tel que pour . Le problème pour trouver un ensemble de frappe minimum d'une famille donnée est NP-difficile en général, car il généralise le problème de couverture de vertex. Maintenant ma question est:H ⋃ n i = 1 S i H ∩ S i ≠ ∅ 1 ≤ i ≤...
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...
Problème connexe: le théorème de Veblen déclare qu '"un graphique admet une décomposition de cycle si et seulement s'il est pair". Les cycles sont disjoints sur les bords, mais pas nécessairement disjoints sur les nœuds. Autrement dit, "L'ensemble des bords d'un graphe peut être partitionné en...
La classe de complexité BQP correspond à des sous-programmes quantiques polynomiaux temporels prenant des entrées classiques et crachant une sortie classique probabiliste. Le conseil quantique le modifie pour inclure des copies de certains états de conseil quantique prédéterminés mais avec des...
Cette question est étroitement liée à un autre article: Transitions de phase dans les problèmes difficiles NP, mais elle est quelque peu différente. Bien que cette question concerne la dureté d'instances particulières de problèmes difficiles NP, il s'agit de classer la difficulté des mêmes...
Considérez le problème suivant: Entrée : un hyperplan , donné par un vecteur et en représentation binaire standard.H= { y ∈ Rn: unTy = b }H={y∈Rn:uneTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}a ∈ Znune∈Zn\mathbf{a} \in \mathbb{Z}^nb ∈ Zb∈Zb \in \mathbb{Z} Sortie :x ∈ Zn=...
Quels sont les problèmes non triviaux où nous savons que l'algorithme actuel que nous avons est asymptotiquement optimal? (Pour les machines de turing) Et comment cela est-il
Préambule. La classe de complexité AM sont les problèmes qui peuvent être résolus par un système de preuve interactif à deux tours entre un prouveur "Merlin" et un vérificateur "Arthur". Un problème - qui teste certaines propriétés d'un objet X - est dans AM si: Pour les instances OUI , pour un...
L' algorithme Weisfeiler-Lehman 1-dim (WL) est communément appelé algorithme d'étiquetage canonique ou de raffinement des couleurs. Cela fonctionne comme suit: La coloration initiale est uniforme, C 0 ( v ) = 1 pour tous les sommets v ∈ V ( G ) ∪ V ( H ) .C0C0C_0C0( v ) = 1C0(v)=1C_0(v) = 1v ∈ V( G...
Considérons le problème suivant: étant donné un graphe de requête et un graphe de référence G ′ = ( V ′ , E ′ ) , nous voulons trouver la cartographie injective f : V → V ′ qui minimise le nombre d'arêtes ( v 1 , v 2 ) ∈ E tel que ( f ( v 1 ) , f ( v 2 ) )G=(V,E)G=(V,E)G = (V,...
Quelle est la complexité de calcul du problème suivant: étant donné deux matrices complexes et vérifiez s'il existe une matrice de permutation telle que: n×nn×nn\times nAAABBBPPPB=PAPT.B=PAPT.B = P A P^T. Si cela aide, on peut supposer que et B sont hermitiens (ou même que A et B sont réels et...