Il y a la théorie algorithmique des graphes / théorie des nombres / combinatoire / théorie de l'information / théorie des jeux. Existe-t-il une analyse mathématique algorithmique? Selon wiki, l'analyse mathématique comprend les théories de la différenciation, de l'intégration, de la mesure, des...
Existe-t-il un résultat connu sur la classe de complexité de 1-en-3-SAT avec un nombre restreint d'occurrences variables? J'ai trouvé la réduction parcimonieuse suivante avec Peter Nightingale, mais je veux citer quelque chose si cela est connu. Voici l'astuce que nous avons trouvée. Cela montre...
Un antichaîne dans un DAG est un sous - ensemble de sommets qui sont inaccessibles par paires, à savoir, il n'y a pas tel que est accessible à partir de dans . D'après le théorème de Dilworth dans la théorie de l'ordre partiel, on sait que si DAG n'a pas d'antichaîne de taille , alors il peut être...
Soit un langage et une fonction sur deux paramètres avec la propriété que pour tout et , renvoie un élément de si et seulement si et sont des éléments de :f : Σ ⋆ × Σ ⋆ → Σ ⋆ x y f L x y LLLLF: Σ⋆× Σ⋆→ Σ⋆f:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starXxxyyyFFfLLLXXxyyyLLL F( x ,y)...
La logique monadique du premier ordre, également connue sous le nom de classe monadique du problème de décision, est l'endroit où tous les prédicats prennent un argument. Il a été démontré qu'il est décidable par Ackermann et est NEXPTIME complet . Cependant, des problèmes comme SAT et SMT ont des...
J'ai un ensemble de nnn vecteurs binaires S={s1,…,sn}⊆{0,1}k∖{1k}S={s1,…,sn}⊆{0,1}k∖{1k}S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\} et un vecteur cible t=1kt=1kt = 1^k qui est le vecteur tout-en-un. Conjecture: si peut être écrit comme une combinaison linéaire d'éléments de S...
Je m'intéresse au problème classique INCLUSION DE LA LANGUE RÉGULIÈRE. Étant donné une expression régulière , nous notons L ( E ) le langage régulier qui lui est associé. (Les expressions régulières sont sur un alphabet fixe Σ , avec les opérations union, Kleene-star et concaténation.)EEEL (...
J'ai lu des informations sur la substitution héréditaire pour le calcul lambda simple et pour le cadre logique avec des termes et des types distincts. Je me demande, existe-t-il des exemples de substitution héréditaire dans un système typé de façon dépendante avec une hiérarchie d'univers?...
Plus précisément, je demande des ressources pour en savoir plus sur les systèmes d'apprentissage automatique qui peuvent mettre à jour leurs réseaux de croyances respectifs (ou équivalent) pendant le fonctionnement. J'en ai même rencontré quelques-uns, même si je n'ai pas réussi à les mettre en...
Quels articles sur la gestion des erreurs dans les systèmes distribués
Tout d'abord, je ne sais toujours pas si la théorie est bien adaptée à cette question, donc je ne serai pas offensé si la foule pense que ce n'est pas le cas ... Dans le marketing des moteurs de recherche, plusieurs problèmes sont intéressants. La conception de mécanismes d'enchères équitables (et...
Cette question va dans le même sens que les discours inspirants pour les élèves de dernière année du secondaire . Mon doctorat. conseiller m'a demandé de donner une conférence inspirante pour le nouveau M.Sc. élèves. Le sujet est les fondements de la cryptographie , ce qui est mieux illustré par le...
Je m'intéresse à des exemples de constructions dans la théorie de la complexité qui sont meilleures que des constructions aléatoires. Le seul exemple d'une telle construction que je connaisse est dans le domaine des codes correcteurs d'erreurs. Les codes à géométrie algébrique sont meilleurs dans...
Un programme span est une manière linéaire-algébrique de spécifier une fonction booléenne présentée ici . Récemment, ce modèle a été utilisé pour montrer que la méthode de l'adversaire négatif fournit une caractérisation étroite (au moins jusqu'à ) de la complexité des requêtes quantiques.Journaln...
Bien que les séparations exponentielles entre la complexité des requêtes quantiques à erreurs limitées ( ) et la complexité des requêtes déterministes ( D ( f ) ) ou la complexité des requêtes randomisées à erreurs limitées ( R ( f ) ) soient connues, elles ne s'appliquent qu'à certaines fonctions...
Il y a eu pas mal de travail sur les problèmes de calcul pour les commandes partielles (par exemple, la reconnaissance, le nombre de sauts, la reconnaissance du graphe de comparabilité, etc.). Je suis curieux de savoir quel travail spécifique aux réseaux a été fait. J'ai cherché autour et je n'ai...
Je suis curieux de savoir si quelqu'un pourrait recommander du matériel supplémentaire pour acquérir une compréhension plus approfondie de l'article: " Quelques résultats et problèmes sur les inégalités quantiques de type Bell - Tsirelson ". Plus précisément, quelque chose qui pourrait élaborer un...
Voici une question "piste B" s'il y en a jamais eu. Résumé: la première chose à laquelle je pense lorsque j'essaie de donner une sémantique à des programmes non déterministes se traduit par une sémantique où je ne peux pas prouver les choses sur les boucles qui ne terminent que la non-déterminisme....
Ma question porte sur l'équivalence de la sécurité des différentes fonctions unidirectionnelles candidates qui peuvent être construites en fonction de la dureté de l'affacturage. En supposant que le problème de FACTEUR: [Étant donné pour des nombres premiers aléatoires P , Q < 2 n , trouver P ,...
Étant donné un graphique mixte avec les arêtes et les arcs , trouvez une correspondance dans qui minimise le nombre d'arcs dans , où est obtenu à partir de en contractant les sommets correspondants et en supprimant arcs parallèles.G=(V,E,A)G=(V,E,A)G=(V,E,A)EEEAAAEEEG/MG/MG/MG/MG/MG/MGGG (La...