Cette question a été migrée à partir de Computer Science Stack Exchange car il est possible d'y répondre sur Theoretical Computer Science Stack Exchange. Migré il y a 3 ans . Dans l'article scientifique de 2016 " Réalisation d'un algorithme de Shor évolutif " [ 1 ], les auteurs factorisent 15 avec...
Regardons l'avenir dans une trentaine d'années. Soyons optimistes et supposons que les domaines liés à l'apprentissage automatique continuent de se développer aussi rapidement que ce que nous avons vu au cours des 10 dernières années. Ce serait formidable, mais alors quel serait le rôle de...
Je fixe un langage régulier sur un alphabet , et je considère le problème suivant que j'appelle la planification de la lettre pour . De manière informelle, l'entrée me donne lettres et un intervalle pour chaque lettre (c'est-à-dire une position minimale et maximale), et mon objectif est de placer...
Cela fait plus d'un an depuis sa rétractation et sa correction de janvier 2017. Y a-t-il des nouvelles? Sinon, est-ce normal que la validation prenne autant de temps? Je m'attendrais à ce qu'il retienne beaucoup d'attention Quelqu'un de remarquable a-t-il parlé pour soutenir / douter du résultat...
La preuve récente et incroyablement lisse de la conjecture de sensibilité repose sur la construction explicite * d'une matrice , définie récursivement comme suit: et, pour , En particulier, il est facile de voir que pour tout .An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times...
La formulation exacte du titre est due à Anand Kulkarni (qui a proposé la création de ce site). Cette question a été posée à titre d'exemple, mais je suis incroyablement curieux. Je connais très peu de choses sur la géométrie algébrique, et en fait, je n'ai aussi qu'une compréhension superficielle...
x∈Rnx∈Rnx \in \mathbb{R}^n∥x∥0<k‖x‖0<k\|x\|_0 < kAxAxAxAAARRRnnn matrice réelle où nous voulons . La magie de la détection compressée est que l'on peut explicitement construire telle sorte qu'il permet une récupération exacte rapide (temps quasi-linéaire) de toutR≪nR≪nR \ll nAAAkkk-sparse xxx...
Scott Aaronson a proposé un défi intéressant : pouvons-nous utiliser des superordinateurs aujourd'hui pour aider à résoudre les problèmes de CS de la même manière que les physiciens utilisent de grands collisionneurs de particules? Plus concrètement, ma proposition est de consacrer une partie de la...
C'est dans la ligne des " Algorithmes du livre ". Bien que les réductions soient également des algorithmes, je pensais qu'il était douteux que l'on pense à une réduction en réponse à la question sur les algorithmes du livre. D'où une requête distincte! Les réductions de toutes sortes sont les...
Le théorème original de la hiérarchie temporelle non déterministe est dû à Cook (le lien est à S. Cook, Une hiérarchie pour la complexité temporelle non déterministe , JCSS 7 343–353, 1973). Le théorème stipule que pour tout nombre réel et , si alors NTIME ( ) est strictement contenu dans NTIME (...
Voici quelques façons d'analyser le temps d'exécution d'un algorithme: 1) Analyse du pire des cas: temps d'exécution sur la pire instance. 2) Analyse de cas moyen: temps d'exécution prévu sur une instance aléatoire. 3) Analyse amortie: durée moyenne d'exécution sur la pire séquence d'instances. 4)...
Quelles sont les références de base? Existe-t-il de bonnes enquêtes de haut niveau sur SGT et ses applications à CS en général et à l'apprentissage machine en
En 1999, Petra Schuurman et Gerhard J. Woeginger ont publié l'article "Algorithmes d'approximation du temps polynomiaux pour la planification des machines: dix problèmes ouverts" . Depuis lors, à ma connaissance, des critiques qui concerneraient très exactement la même liste de problèmes ne sont...
Je ne comprends pas très bien pourquoi presque tous les solveurs SAT utilisent CNF au lieu de DNF. Il me semble que résoudre SAT est plus facile en utilisant DNF. Après tout, il vous suffit de parcourir l'ensemble des implicants et de vérifier si l'un d'eux ne contient pas à la fois une variable et...
Que sait-on de la complexité temporelle du problème suivant, que nous appelons 3-MUL? Étant donné un ensemble de entiers, y a-t-il des éléments tels que ?SSSnnna,b,c∈Sa,b,c∈Sa,b,c\in Sab=cab=cab=c Ce problème est similaire au problème 3-SUM, qui demande s'il y a trois éléments tels que (ou de...
Peter Shor a soulevé un point intéressant concernant une tentative de répondre à une question précédente sur la complexité de la résolution du cube Rubiks . J'avais posté une tentative assez naïve de montrer qu'elle doit être contenue dans NP. Comme Peter l'a souligné, mon approche échoue dans...
Cette question concerne la relation entre la multiplication normale des nombres binaires et la multiplication polynomiale mod 2. Pour rendre la question concrète, j'aimerais idéalement savoir s'il existe une meilleure solution à la question de Knuth vol. 2, 3e édition, page 420 que celle donnée...
Ces derniers mois, j'ai commencé à m'exprimer sur le choix social, le théorème de la flèche et les résultats associés. Après avoir lu les résultats séminaux, je me suis demandé ce qui se passe avec les préférences d'ordre partiel, la réponse est dans l'article de Pini et al. : Agrégation de...
Je viens de réaliser que je supposais que la réponse à ma question était "oui" mais je n'ai pas de bonne raison. J'imagine qu'il y a peut-être un garbage collector qui n'introduit que le ralentissement pire des cas. Y a-t-il une référence définitive que je peux citer? Dans mon cas, je travaille sur...
Cette question fait suite à la question sur les algorithmes d'ADN posée par Aadita Mehra . Dans ses commentaires, Joe Fitzsimmons a déclaré, en partie: [L] e rayon du système doit évoluer proportionnellement à la masse pour éviter cela. La puissance de calcul évolue au plus linéairement dans la...