Considérons le modèle suivant: une chaîne de n bits r = r 1 ... r n est choisie uniformément au hasard. Ensuite, chaque indice i∈ {1, ..., n} est placé dans un ensemble A avec une probabilité indépendante 1/2. Enfin, un adversaire est autorisé, pour chaque i∈A séparément, à retourner r i s'il le...
Existe-t-il un exemple d'une classe de graphes pour laquelle le problème de coloration des sommets est en P mais l'ensemble indépendant est le problème est NP
Une matrice est dite totalement régulière si toutes ses sous-matrices carrées ont un rang complet. De telles matrices ont été utilisées pour construire des superconcentrateurs. Quelle est la complexité de décider si une matrice donnée est totalement régulière sur les logiques? Sur des champs finis?...
Une propriété de base des espaces vectoriels est qu'un espace vectoriel V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n de dimension n−dn−dn-d peut être caractérisé par ddd contraintes linéaires linéairement indépendantes - c'est-à-dire qu'il existe ddd vecteurs linéairement indépendants...
Feedback Vertex Set est NP-complete pour les graphiques généraux. Il est connu qu'il est NP-complet pour les graphiques bornés de degré 8 en raison d'une réduction de la couverture des sommets. L' article de Wikipédia indique qu'il est résoluble en temps poly pour les graphiques bornés de degré 3...
Peut-on calculer une porte de seuil à bits par des circuits de taille polynomiale (fan-in illimité) de profondeur lg nnnn ? Alternativement, pouvons-nous compter le nombre de 1 dans les bits d'entrée en utilisant ces circuits?lgnlglgnlgnlglgn\frac{\lg n}{\lg \lg n} Est ?T C0⊆ A l t T i m e (O(...
J'étudie actuellement les mathématiques. Cependant, je ne pense pas vouloir devenir mathématicien professionnel à l'avenir. Je pense appliquer mes connaissances en mathématiques pour faire de la recherche en intelligence artificielle. Cependant, je ne sais pas combien de cours de mathématiques je...
Quelles sont les limites de la programmation fonctionnelle totale? Il n'est pas complet de Turing, mais prend toujours en charge un large sous-ensemble des programmes possibles. Y a-t-il des constructions importantes que vous pourriez écrire dans un langage complet de Turing, mais pas dans un...
En informatique distribuée, le problème du consensus semble être l'un des sujets centraux qui a attiré des recherches intensives. En particulier, le document "Impossibilité d'un consensus distribué avec un processus défectueux" a reçu le PODC Influential Paper Award 2001 . Alors pourquoi le...
Je recherche un document d'enquête ou un livre couvrant les résultats sur la complexité spatiale des opérations d'algèbre linéaire courantes telles que le classement matriciel, le calcul des valeurs propres, etc. est plus facile de tracer les résultats temporels. J'apprécie toute référence en la...
Il est bien connu que les combinateurs S et K sont Turing Complete. Existe-t-il des combinateurs suffisants pour produire (uniquement) les fonctions récursives
Quelle serait une bonne preuve informelle / intuitive pour «toucher le point» de la dualité LP? Comment montrer au mieux que la fonction objectif minimisée est bien le minimum avec une manière intuitive de comprendre la limite? La façon dont on m'a enseigné la dualité n'a conduit qu'à une seule...
J'ai une éducation mathématique de premier cycle raisonnable, mais je n'ai jamais été à 100% à l'aise avec l'algèbre abstraite (les mathématiques des groupes, des anneaux, des champs, etc.). Je pense que c'était en partie parce que j'avais besoin de voir des applications et toutes celles que je...
Quelle est la complexité temporelle (et non la complexité des requêtes) de l'algorithme de Grover? Il me semble clair qu'il s'agit de car il existe des itérations et chaque itération nécessite l'utilisation de l'opération de réflexion qui à son tour prend du temps utilisant n'importe quel ensemble...
Soit le nombre d'arbres couvrant un graphe à sommets. Il existe un algorithme qui calcule dans les opérations arithmétiques . Cet algorithme consiste à calculer , où Q est le laplacien de G et J est la matrice constituée uniquement de 1 . Pour plus d'informations sur cet algorithme, voir Biggs -...
Je m'intéresse au problème suivant: étant donné les matrices entières décident si chaque produit infini de ces matrices est finalement égal à la matrice zéro.A1,A2,…,AkA1,A2,…,AkA_1,A_2, \ldots, A_k Cela signifie exactement ce que vous pensez qu'il fait: nous dirons que l'ensemble des matrices a la...
En calcul quantique adiabatique (AQC), on code la solution d'un problème d'optimisation à l'état fondamental d'un [problème] hamiltonien . Pour arriver à cet état fondamental, vous commencez dans un état initial (fondamental) facilement refroidissable avec Hamiltonian H i et "recuit" (perturber...
Je m'intéresse au concept de "complétude r-Turing", tel que défini par Axelsen et Glück (2011) . Un système est r-Turing complet s'il peut calculer le même ensemble de fonctions qu'une machine de Turing réversible, sans produire de données "poubelles". C'est la même chose que de pouvoir calculer...
Je voudrais prouver (ou réfuter) la conjecture suivante: Conjecture : un automate à deux compteurs (2CA) ne peut pas décider de la langue suivante: les représentations ternaire et binaire de n ont à la fois une longueur paire ou une longueur impaire }L = { n ∣L={n∣L = \{ n \mid nnn}}\} Un 2CA peut...
Contexte: Considérons le modèle habituel à deux parties de la complexité de la communication où Alice et Bob reçoivent des chaînes de nnn bits Xxx et yyy et doivent calculer une fonction booléenne F( x , y)f(x,y)f(x,y) , où F: { 0 , 1 }n× { 0 , 1 }n→ { 0 , 1 }f:{0,1}n×{0,1}n→{0,1}f:\{0,1\}^n \times...