Étant donné nnn entrées x0,…,xn−1x0,…,xn−1x_0, \ldots, x_{n-1} , nous construisons un réseau de tri aléatoire avec mmm portes en choisissant itérativement deux variables xi,xjxi,xjx_i, x_j avec i<ji<ji < j et en ajoutant une porte de comparaison qui les échange si xi>xjxi>xjx_i > x_j ....
Quelle est la complexité de décider si un intervalle des nombres naturels contient un nombre premier? Une variante du tamis d'Ératosthène donne un algorithme O~(L)O~(L)\tilde O(L) , où LLL est la longueur de l'intervalle et ∼∼\sim cache les facteurs poly-logarithmiques au point de départ de...
Considérez le problème de décision suivant Entrée : un CNF ΦΦ\Phi monotone et un DNF monotone ΨΨ\Psi. Question : Φ→ΨΦ→Ψ\Phi \to \Psi une tautologie? Vous pouvez certainement résoudre ce problème en temps O(2n⋅poly(l))O(2n⋅poly(l))O(2^n \cdot \mathrm{poly}(l)) , où nnn est le nombre de variables...
Existe-t-il une catégorie de correctifs qui ressemble à peu près à ceci: Les objets sont des chaînes dans un alphabet de base Les morphismes sont des scripts d'édition ("diffs" ou "patches") entre les chaînes Je m'intéresse à ces questions: Existe-t-il une notion catégorique de script d'édition...
J'ai récemment appris la conjecture gourmande du problème de chaîne la plus courte . Dans ce problème, on nous donne un ensemble de chaînes s1,…,sns1,…,sns_1,\dots, s_n et nous voulons trouver la chaîne la plus courte c'est-à-dire telle que chaque apparaisse comme une sous-chaîne de .ssssisis_isss...
J'ai un jeu de données qui est un certain nombre d'objets disposés dans une grille 2D. Je sais que j'ai un ordre strict, augmentant à mesure que vous avancez de gauche à droite dans chaque ligne, et augmentant de haut en bas dans chaque colonne. Par exemple, 1 2 3 4 6 7 5 8 9 Puis-je améliorer le...
Les graphes de Paley P q sont ceux dont l'ensemble des sommets est donné par le champ fini GF (q), pour les puissances premières q≡1 (mod 4), et où deux sommets sont adjacents si et seulement s'ils diffèrent de 2 pour certains a ∈ GF (q). Dans le cas où q est premier, le champ fini GF (q) n'est que...
Il est connu grâce à Immerman et Szelepcsényi que si f = Ω ( log ) (même pour les fonctions constructibles non spatiales).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) Dans le même article, Immerman déclare que la hiérarchie alternative de...
Quels sont les problèmes du monde réel qui ont été résolus en utilisant un algorithme génétique? Quel est le problème? Quel est le test de condition physique utilisé pour résoudre ce
En termes simples: quelle est la correspondance entre les machines de Turing avec oracles et les familles de circuits uniformes avec oracles? Comment ces derniers sont-ils définis afin d'obtenir le même modèle de calcul, pour une machine Oracle Turing donnée? Cela peut être une question...
Il est facile de vérifier que, étant donné la grille dimensionnelle d des points entiers , avec la contiguïté régulière, on peut trouver un séparateur de taille n d - 1 (il suffit de choisir n'importe quel hyperplan central et de supprimer tout ses sommets). Il n'est pas non plus trop difficile...
Suite à la discussion sur les bornes inférieures pour 3SAT [ 1 ], je me demande quels sont les principaux résultats de borne inférieure formulés comme des compromis espace-temps. J'exclus des résultats tels que, disons, le théorème de Savitch; une bonne entrée se concentrerait sur un seul problème...
Ceci est une question inspirée par le problème de la coupe H sans . Étant donné un graphe, une partition de son ensemble de sommets en r parties V 1 , V 2 , … , V r est sans H si G [ V i ] n'induit pas une copie de H pour tout i , 1 ≤ i ≤ rVVVrrrV1,V2,…,VrV1,V2,…,VrV_1, V_2, \ldots,...
Les inégalités de type Chernoff sont utilisées pour montrer que la probabilité qu'une somme de variables aléatoires indépendantes s'écarte significativement de sa valeur attendue est exponentiellement faible dans la valeur attendue et l'écart. Existe-t-il une inégalité de type Chernoff pour toute...
Donc, j'ai environ 100-200 matrices booléennes carrées très clairsemées avec une longueur de côté ~ plusieurs dizaines, et j'ai besoin de calculer leur produit. Je sais que si je les multiplie en série, le produit restera généralement aussi clairsemé à chaque étape. Existe-t-il des algorithmes de...
Dans le journal Quantum Random Walks Hit Exponially Faster ( arXiv: quant-ph / 0205083 ) Kempe donne une notion de temps de frappe pour les marches quantiques (dans l'hypercube) qui n'est pas très populaire dans la littérature sur la marche quantique. Il est défini comme suit: One-Shot Quantum...
Dans un article intitulé «Sur le déni dans la chaîne de référence commune et le modèle Oracle aléatoire», Rafael Pass écrit: Nous notons que lors de la démonstration de la sécurité selon la définition standard de la connaissance zéro dans le modèle RO [Oracle aléatoire], le simulateur a deux...
Comme le titre l'indique, quelle est la définition correcte de arbre? Il existe plusieurs articles qui parlent d' arbres et d' arbres partiels comme définitions alternatives pour les graphiques avec une largeur d'arbre bornée, et j'ai vu de nombreuses définitions apparemment incorrectes. Par...
Chong, Han et Lam ont montré que la connectivité st non dirigée peut être résolue sur la PRRE EREW en temps avec des processeurs . Quel est l'algorithme parallèle le plus connu pour la connectivité st dirigée ? Veuillez indiquer le temps d'exécution, l'algorithme déterministe / randomisé et le...
On dit que deux arbres de recherche binaires sont linéairement équivalents lorsqu'ils s'accordent dans leurs traversées dans l'ordre. Le théorème suivant explique pourquoi les rotations d'arbres sont si fondamentales: Soit A et B des arbres de recherche binaires. Alors A et B sont linéairement...