Cette question est similaire à l' une de mes précédentes. Il est connu que est un mineur interdit pour les graphiques de largeur d'arbre au plus .Kt+2Kt+2K_{t+2}ttt Existe-t-il une famille infinie de graphiques bien paramétrés et bien construits (autres que les graphiques complets et les graphiques...
Étant donné , combien de -DNF avec variables et clauses sont tautologiques? (ou combien de -CNF ne sont pas satisfaisants?)k n m km , n , km,n,km, n,
Un réseau de commutation (le nom est inventé) est constitué de trois types de nœuds: un nœud de démarrage un nœud d'extrémité un ou plusieurs nœuds Switch Le nœud de commutation a 3 sorties: Gauche, Haut, Droite; a deux états L et R et un état cible TL ou TR . Chaque commutateur peut être traversé...
Disons qu'un graphe est ( a , b ) -connexe si la suppression de tout un des sommets et des b arêtes de G feuilles toujours un graphe connexe. Par exemple, un graphe connecté k , selon la définition standard, est connecté ( k - 1 , 0 ) , selon la nouvelle définition. Existe-t-il un algorithme...
Contexte: relations entre logique et automates Le théorème de Büchi affirme que la logique monadique du second ordre sur les chaînes (MSO) capture la classe des langages réguliers. La preuve montre en fait que MSO existentiel ( exist ou EMSO ) sur les chaînes est suffisant pour capturer des langues...
Supposons que nous avons construit un ordinateur quantique universel. À l'exception des problèmes liés à la sécurité (cryptographie, confidentialité, ...), quels problèmes actuels du monde réel peuvent bénéficier de son utilisation? Je suis intéressé par les deux: problèmes actuellement insolubles...
Je cherche un algorithme pour fusionner deux arbres de recherche binaires de taille et de plage arbitraires. La manière évidente de procéder pour l'implémenter serait de trouver des sous-arbres entiers dont la plage peut s'insérer dans un nœud externe arbitraire dans l'autre arbre. Cependant, le...
Il y a de nombreuses années, j'ai entendu dire que le calcul du NFA minimal (automate fini non déterministe) à partir d'un DFA (déterministe) était une question ouverte, par opposition à la direction inverse qui est connue depuis des décennies et est bien étudiée avec un efficace algorithme....
(également demandé ici , pas de réponses) Un expanseur quantique est une distribution sur le groupe unitaire avec la propriété que: a) , b) , où \ mu_H est la mesure de Haar. Si , au lieu des distributions sur unitaries nous considérons les distributions sur les matrices de permutation, il est...
Un labyrinthe fractal est un labyrinthe qui contient des copies de lui-même. Par exemple, le suivant par Mark JP Wolf de cet article : Commencez au MOINS et dirigez-vous vers le PLUS. Lorsque vous entrez dans une petite copie du labyrinthe, assurez-vous d'enregistrer le nom de la lettre de cette...
Le calcul quantique limité dans le temps est évidemment très intéressant. Qu'en est-il du calcul quantique limité dans l'espace? Je connais de nombreux résultats intéressants pour le calcul quantique avec des limites d'espace sublogarithmiques et divers types de modèles d'automates quantiques. D'un...
Pour autant que je sache, la plupart des implémentations de la génération de nombres pseudo-aléatoires utilisent des méthodes telles que les registres de rétroaction à décalage linéaire (LSFR), ou ces algorithmes "Mersenne Twister". Bien qu'ils passent de nombreux tests statistiques (heuristiques),...
Les automates déterministes bidirectionnels à un compteur de 2dca (Petersen, 1994) peuvent reconnaître le langage unaire suivant: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Existe-t-il une autre langue unaire non triviale...
Je lis sur les classes de graphiques pour lesquels Graphique Isomorphisme ( ) est en . Un de ces cas est des graphiques de valence bornée (maximum sur le degré de chaque sommet) comme expliqué ici . Mais je l'ai trouvé trop abstrait. Je serais reconnaissant si quelqu'un pouvait me suggérer quelques...
Les graphes planaires ont le genre zéro. Les graphiques embarquables sur un tore ont un genre au maximum 1. Ma question est simple: Y a-t-il des problèmes qui peuvent être résolus polynomialement sur les graphes planaires mais NP-dur sur les graphes du genre un? Plus généralement, y a-t-il des...
J'ai enseigné bornes inférieures aujourd'hui, et l'un des étudiants a demandé la raison du nom . L'explication officielle est que le "A" signifie "Alternance".AC0AC0AC^0ACACAC Je me souviens vaguement, il y a de nombreuses années, que Nick Pippenger Steve Cook a nommé après Nick Pippenger (la...
Version courte. La preuve originale que # 2-SAT est #P -complete montre, en fait, que les instances de # 2-SAT qui sont à la fois monotones (n'impliquant la négation d'aucune variable) et bipartites (le graphique formé par les clauses sur le est un graphe bipartite) sont #P -hard. Ainsi, les deux...
Nous savons que les programmes linéaires (LP) peuvent être résolus exactement en temps polynomial en utilisant la méthode ellipsoïde ou une méthode de point intérieur comme l'algorithme de Karmarkar. Certains LP avec un nombre super-polynomial (exponentiel) de variables / contraintes peuvent...
La plupart des sites que j'ai visités en lisant sur ce sujet intéressant indiquent quelque chose dans le sens "les seuls pouvoirs de deux (autres que 2 lui-même) qui se produisent dans cette séquence sont ceux avec l'exposant principal" (MathWorld) ou "Après 2, cette séquence contient les pouvoirs...
Ceci fait suite à une question récente posée par A. Pal: Résolution de programmes semi-définis en temps polynomial . Je reste perplexe sur le temps d'exécution réel des algorithmes qui calculent la solution d'un programme semi-défini (SDP). Comme Robin l'a souligné dans son commentaire sur la...