Étant donné le coprime , pouvez-vous calculer rapidementa,ba,ba, bminx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Ici x,yx,yx, y sont des entiers. Évidemment, prendre x=y=0x=y=0x = y = 0 donne une réponse sans intérêt; en général, à quel point ces pouvoirs peuvent-ils se...
Après les succès de plus en plus récents des réseaux de neurones dans les jeux de société, on sent que le prochain objectif que nous nous sommes fixé pourrait être quelque chose de plus utile que de battre les humains dans Starcraft. Plus précisément, je me demandais si Les réseaux de neurones...
Étant donné une fonction booléenne , nous avons le groupe d'automorphisme A u t ( f ) = { σ ∈ S n ∣ ∀ x , f ( σ ( x ) ) = f ( x ) } .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Existe-t-il des bornes connues sur ?...
Le théorème de Cantor déclare que Pour tout ensemble A, l'ensemble de tous les sous-ensembles de A a une cardinalité strictement supérieure à A lui-même. Est-il possible d'encoder quelque chose comme ça en utilisant uniquement des types / propositions sans se référer aux ensembles ZFC? Un code ou...
Je suis un chercheur qui travaille dans la théorie des algorithmes et de la complexité, j'utilise la complexité paramétrée dans une certaine mesure. Il me semble que les chercheurs en complexité paramétrée sont très actifs (je ne veux pas dire que d'autres ne le sont pas) en termes de nombre de...
Est-ce que quelqu'un sait d'où viennent les noms System "F" et System "T"? Je ne demande pas qui a introduit ces noms (Girard System F et Gödel System T), mais ce que le "F" et le "T"
Il est connu que Ford-Fulkerson ou Edmonds-Karp avec l'heuristique fat pipe (deux algorithmes pour max-flow) ne doivent pas s'arrêter si certains des poids sont irrationnels. En fait, ils peuvent même converger vers la mauvaise valeur! Cependant, tous les exemples que j'ai pu trouver dans la...
Je suis curieux de savoir comment vous avez vu la non-uniformité être utile dans le calcul. Une façon est le caractère aléatoire, comme dans , et une autre est des tables de recherche qui sont utilisées pour montrer que toutes les langues ont des circuits non uniformes.B PP⊆ P/ polyBPP⊆P/polyBPP...
Braverman a montré que les distributions qui sont (logmϵ)O(d2)(logmϵ)O(d2)(log \frac{m}{\epsilon})^{O(d^2)}-indépendant indépendant ϵϵ\epsilon-fond profondeur ddd AC0AC0AC^0 circuits de taille mmm en "collant ensemble" l'approximation de Smolensky et l'approximation de Fourier de...
Soit un alphabet fini. Pour un langage donné le monoïde syntaxique est une notion bien connue en théorie formelle du langage. De plus, un monoïde reconnaît un langage ssi il existe un morphisme tel que .L ⊆ A ∗ M ( L ) M L φ : A ∗ → M L = φ - 1 ( φ ( L ) ) )UNEAAL ⊆ A∗L⊆UNE∗L \subseteq A^{\ast} M(...
Dans Une théorie intuitioniste des types de Martin-Löf : partie prédicative, il est prouvé que la vérification de type est décidable sous réserve d' un être typable en premier lieu, en prouvant un théorème de normalisation pour les termes typables fermés. D'un autre côté, je l'ai vu écrit à...
Quelles sont les limites supérieures asymptotiques les plus connues sur les tailles des preuves vérifiables de manière probabiliste? Idéalement, je recherche une enquête contemporaine sur cette large question, mais s'il n'y en a pas, je suis particulièrement intéressé par l'inapproximabilité du...
Le théorème de Robertson – Seymour dit que toute famille gg\mathcal G de graphes mineurs peut être caractérisée par un nombre fini de mineurs interdits. Existe-t-il un algorithme qui, pour une entrée gg\mathcal G délivre les mineurs interdits ou est-ce indécidable? Évidemment, la réponse pourrait...
J'ai du mal à comprendre la preuve d'une forte normalisation pour le calcul des constructions. J'essaye de suivre la preuve dans le papier de Herman Geuvers "Une preuve courte et flexible de Normalisation Forte pour le Calcul des Constructions". Je peux bien suivre le raisonnement principal....
Il existe un certain nombre de modèles différents pour définir les transformations entre les langues. Les transducteurs à états finis et les transformations de graphes définissables par MSO sur des graphes à cordes sont les deux que je connais le mieux. Nous savons que les transducteurs à états...
S'il y a des résultats sur la résolution des problèmes de langage formel en utilisant l'analyse mathématique, les mathématiques continues. Par exemple, résoudre le problème de non-vacuité d'intersection pour une langue sans contexte et une langue
Deux piles peuvent être mises en œuvre efficacement en utilisant un tableau de taille fixe: la pile # 1 commence à partir de l'extrémité gauche et croît vers la droite, et la pile # 2 commence à partir de l'extrémité droite et croît vers la gauche. Est-ce la même chose possible pour trois piles?...
Dernièrement, je me suis intéressé à la géométrie algébrique et j'ai commencé à lire dessus. Je connais encore très peu ce domaine, mais je veux savoir s'il a un lien avec mon domaine principal, la théorie des types et les langages de programmation. Je sais que la topologie algébrique a beaucoup...
Il existe un type de résultats dans TCS généralement appelé résultats d'amorçage . En général, il a la forme Si la proposition est vraie, alors la proposition est vraie.UNEAAUNE′A′A' où et sont des propositions qui se ressemblent, et est apparemment "plus faible" que , c'est la raison pour laquelle...
Pour de nombreux problèmes, l'algorithme avec la meilleure complexité asymptotique a un très grand facteur constant qui est caché par une grande notation O. Cela se produit dans la multiplication matricielle, la multiplication d'entiers (en particulier, le récent algorithme de multiplication...