Y a-t-il des problèmes dans CS où aucun algorithme efficace n'est connu, malgré l'existence de théorèmes prouvant que de tels algorithmes efficaces doivent exister? Comment s'appellent ces problèmes? Où puis-je en savoir
Dans l'article "LA COMPLEXITÉ DES PROBLÈMES DE SATISFACABILITÉ" de Thomas J. Schaefer, l'auteur a mentionné que This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the...
Un tenseur est une généralisation de vecteurs et de matrices à des dimensions supérieures et le rang d'un tenseur généralise également le rang d'une matrice. A savoir, le rang d'un tenseur TTT est le nombre minimum de rang un tenseurs cette somme à TTT . Un vecteur et une matrice sont des tenseurs...
Quelqu'un connaît-il des références qui définissent précisément le lien entre l' algorithme d'unification et l'élimination gaussienne? Je suis particulièrement intéressé par la relation entre les substitutions triangulaires et les décompositions LU. Wayne Snyder et Jean Gallier mentionnent cette...
Lors de la conception d'algorithmes d'approximation, on résout parfois un programme semi-fini suivi d'une étape d'arrondi. Un exemple souvent utilisé pour illustrer cela est Max-Cut. (Voir par exemple les algorithmes d'approximation de Vijay Vazirani.) Existe-t-il de bonnes sources ou enquêtes...
Je recherche une référence pour le résultat suivant: Ajouter deux entiers dans la représentation factorisée est aussi difficile que factoriser deux entiers dans la représentation binaire habituelle. (Je suis presque sûr que c'est là-bas parce que c'est quelque chose que je me demandais à un moment...
Soit un graphe. Pour un sommet , définir pour être le (ouvert) voisinage de dans . Autrement dit, . Définissez deux sommets dans comme des jumeaux si et ont le même ensemble de voisins, c'est-à-dire si .G=(V,E)g=(V,E)G=(V,E)x∈VX∈Vx\in
Je me demande s'il y a une justification pour croire que ou pour croire que N L ≠ L ?NL = LNL=LNL=LNL ≠ LNL≠LNL\neq L On sait que . La littérature sur dérandomisation de R L est assez convaincant que R L = L . Quelqu'un connaît-il des articles ou des idées convaincants que N L ≠ L ?NL ⊂ L2NL⊂L2NL...
Existe-t-il une bonne enquête qui compare différents extracteurs, concentrateurs et superconcentrateurs et présente les meilleures méthodes en termes de compromis entre le caractère aléatoire, le temps et l'espace?
J'ai vu (et entendu) qu'il a affirmé qu'il est sûr d'ajouter l'axiome classique du milieu exclu à Coq, mais je n'arrive pas à trouver un document soutenant cette affirmation. Les articles que je vois répertoriés sur le wiki Coq sur le milieu exclu montrent une incohérence avec l'ensemble...
Je recherche des langages qui ne sont "probablement pas sans contexte" mais nous ne sommes pas en mesure de le (dé) prouver en utilisant des techniques standard connues. Y a-t-il une enquête récente sur le sujet ou une section de problème ouvert d'une conférence récente? Il n'y a probablement pas...
Il existe de nombreux endroits où les nombres ππ\pi et ( 1 + 5-√) / 2(1+5)/2(1+\sqrt5)/2apparaissent. Je suis curieux de connaître les algorithmes dont le temps d'exécution contient le nombre d'or ouππ\pidans
capture l'idée d'une parallélisation efficace, et une interprétation de celui-ci est les problèmes qui peuvent être résolus dans le temps O ( log c n ) en utilisantdes processeurs parallèles O ( n k ) pour certaines constantes c , k . Ma question est de savoir s'il existe une classe de complexité...
J'ai rencontré le résultat suivant lors de mes recherches. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 oùetsont choisis au hasard parmi.a1,⋯,am[n]m=ω(n−−√)m=ω(n)m=\omega(\sqrt...
Lorsque j'enseigne les limites de la queue, j'utilise la progression habituelle: Si votre RV est positif, vous pouvez appliquer l'inégalité de Markov Si vous avez l' indépendance et aussi la variance limitée, vous pouvez appliquer l'inégalité de Tchebychev Si chaque VR indépendant a également tous...
Considérez le raisonnement suivant: Soit la complexité de Kolmogorov de la chaîne . Le théorème d'incomplétude de Chaitin dit quexK( x )K(x)K(x)Xxx pour tout cohérent et système formel suffisamment solide , il existe une constante (ne dépendant que du système formel et sa langue) de telle sorte que...
Récemment, j'ai travaillé sur le problème du calcul de la somme approximative d'une liste de nombres non négatifs triés. Pour tout fixe , un schéma d'approximation du temps a été dérivé de telle sorte qu'il donne une approximation pour la somme. Le document est publié sur...
Contexte: Soit u,vu,vu, v deux sommets d'un graphe non orienté . Un ensemble de sommets est un séparateur si et appartiennent à différents composants connectés de . Si aucun sous-ensemble correct d'un séparateur est un séparateur, alors est un séparateur minimal. Un ensemble de sommets est un...
(Il s'agit d'un suivi de cette question et de sa réponse .) J'ai le programme linéaire d'entier (ILP) totalement unimodulaire (TU) suivant. Ici sont tous des entiers positifs donnés dans le cadre de l'entrée. Un sous-ensemble spécifié des variables x i j est mis à zéro, et le reste peut prendre des...
Une chaîne d'addition est une séquence d'entiers positifs où et chaque index , nous avons pour certains indices . La longueur de la chaîne d'addition est ; la cible de la chaîne d'addition est .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i n x n(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dots,...