Le problème de satisfaction est, bien sûr, un problème fondamental en CS théorique. Je jouais avec une version du problème avec une infinité de variables. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Configuration de base. Soit XXX un ensemble de variables non vide et...
Une approche récente de la création d'une monnaie en ligne décentralisée, appelée Bitcoin , a suscité un certain intérêt. L'objectif est d'avoir un moyen de transférer des devises sans autorité centrale et sans double dépense ou contrefaçon. Leur approche consiste à faire en sorte que tous les...
Le calcul quantique est un domaine de recherche actif qui vise à tirer parti de la physique quantique (par exemple l'intrication quantique) pour faire progresser les capacités d'efficacité des ordinateurs (ne modifie pas la thèse de Church-Turing ). Quelles sont les expériences les plus importantes...
Supposons que l'on vous donne un graphe H. connecté, simple et non orienté Le problème de coupe sans H est défini comme suit: Étant donné un graphe simple et non orienté G, existe-t-il une coupure (partition des sommets en deux ensembles non vides, L, R) de sorte que les graphes induits par les...
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é...
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...
Quelles sont les méthodes les plus connues pour la convolution cyclique de longueur nnn sur un petit champ, c'est-à-dire quand |F|≪n|F|≪n|\mathbb{F}| \ll n ? Je suis particulièrement intéressé par les champs de taille constante, ou même . Les déclarations et références générales sur l'efficacité...
En lisant un article sur l'utilisation de méthodes algébriques pour détecter certains sous-graphes induits, il apparaît que l' idéal de bord est un outil important reliant l'algèbre commutative et la théorie des graphes. Comme je ne suis pas familier avec les calculs d'objets algébriques,...
Pour autant que je sache, toutes les règles de pivot déterministes connues pour les algorithmes simplex ont des entrées spécifiques sur lesquelles l'algorithme nécessite un temps exponentiel (ou du moins pas polynomial) pour trouver l'optimum. Appelons ces instances «pathologiques» car généralement...
Je cherche à savoir s'il y a des résultats généraux ou des exemples concernant l'exhaustivité NP du problème de trouver une deuxième solution à un problème NP-complet. Plus précisément, je suis intéressé par tout problème de la forme suivante: Étant donné une solution à une instance d'un problème...
Je suis nouveau dans la théorie des langages de programmation et je cherche une bonne ressource sur une ressource pour la sémantique formelle des langages de programmation. Recherche spécifique de sémantique opérationnelle structurelle. J'ai reçu quelques recommandations de livres. Mais je cherche...
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...
Puisque le terme est surchargé, une brève définition d'abord. Un poset est un ensemble doté d'un ordre partiel . Étant donné deux éléments , nous pouvons définir (jointure) comme leur borne inférieure la plus basse dans , et de même définir (rencontrer) (joindre) comme borne inférieure la plus...
Que faire si l'on sait quelque chose sur la complexité paramétrée du calcul du nombre d'intersection d'un graphe (le plus petit nombre de cliques nécessaires pour couvrir tous ses bords)? Il est connu depuis longtemps pour être NP-complet, et c'est évidemment FPT car il a un noyau: si vous pouvez...
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...
La classe de graphique suivante est-elle connue dans la littérature? La classe de graphes est paramétrée par des entiers positifs et et contient chaque graphe telle sorte que pour chaque sommet , le sous-graphe de induit sur tous les sommets à distance au plus partir de dans a une largeur d'arbre...
On sait que la taille minimale des U_2 calculant la fonction de parité est exactement égale à . La preuve de la borne inférieure est basée sur la méthode d'élimination des portes.U2U2U_23 ( n - 1 )3(n-1)3(n-1) Récemment, j'ai remarqué que la méthode d'élimination de porte fonctionne bien également...
Il est bien connu que si vous lancez n balles dans n cases, le bin le plus chargé est très susceptible d'avoir balles dedans. En général, on peut poser des questions sur balles dans cases. Un article de RANDOM 1998 de Raab et Steger explore cela en détail, montrant qu'à mesure que augmente, la...
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...
On m'a dit qu'il existe de bons algorithmes de temps polynomiaux pour approximer le nombre de chemins simples dans un graphe orienté d'un sommet de départ donné à un sommet de fin donné t . Quelqu'un connaît-il une bonne référence à ce sujet?sssttt Contexte: compter le nombre exact de chemins dans...