Klop, van Oostrom et de Vrijer ont un article sur le calcul lambda avec des motifs. http://www.sciencedirect.com/science/article/pii/S0304397508000571 Dans un certain sens, un modèle est un arbre de variables - bien que je ne le considère que comme un tuple imbriqué de variables, par exemple, ((x,...
Dans l'annexe B de Boosting and Differential Privacy de Dwork et al., Les auteurs indiquent le résultat suivant sans preuve et le qualifient d'inégalité d'Azuma: Soit C1,…,CkC1,…,CkC_1, \dots, C_k des variables aléatoires à valeurs réelles telles que pour tout i∈[k]i∈[k]i \in [k] ,...
Qui a été la première personne à démontrer qu'une langue est en NP si un certificat pour la langue peut être vérifié en temps polynomial? Avons-nous un document qui le prouve formellement? Quand la communauté TCS a-t-elle commencé à mettre l'accent sur le non-déterminisme en faveur de la...
Je veux être très précis. Quelqu'un connaît-il un rejet ou une preuve de la proposition suivante: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...
Toutes mes excuses à l'avance pour cette question douce qui n'a pas de réponse fermée et correcte. C'est probablement le meilleur forum pour poser ma question. Je suis un étudiant diplômé de troisième année dans un groupe théorique d'une école du top 15 aux États-Unis. Jusqu'à présent, je me...
Supposons que l'on vous donne deux automates déterministes push down qui reconnaissent les langages et B et souhaitent déterminer s'il existe un langage régulier R tel que A ⊆ R et R ∩ B = ∅ . Fondamentalement, le défi consiste à déterminer s'il existe un DFA qui peut reconnaître de quelle langue...
Dans la récente préimpression https://arxiv.org/abs/1801.00776 , il est affirmé que nombres réels peuvent être triés dans le temps et l'espace linéaire. L'article semble raisonnable, même si je ne suis pas un expert en algorithmes de tri.nnnO(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Si elle est...
Il y a un chercheur montrant que l'effacement d'un bit doit consommer de l'énergie, maintenant y a-t-il des recherches sur la consommation moyenne d'énergie d'un algorithme avec une complexité de calcul ? Je suppose que la complexité de calcul F ( n ) est corrélée à la consommation moyenne...
Imaginons que nous ayons deux ensembles mmm de points X,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^n . Quelle est la complexité (temporelle) des tests s'ils diffèrent uniquement par la rotation? : il existe une matrice de rotation OOT=OTO=IOOT=OTO=IOO^T=O^TO=I telle que X=OYX=OYX=OY ? Il y a un problème de...
J'ai récemment tenté d'implémenter le Cedille-Core d' Aaron , un langage de programmation minimaliste capable de prouver des théorèmes mathématiques sur ses propres termes. J'ai également prouvé l'induction de types de données codés λ dessus, ce qui a permis de comprendre pourquoi ses extensions...
Existe-t-il une machine de Turing qui peut décider si presque toutes les autres machines de Turing s'arrêtent? N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\| \cdot \| f(i)=∥{n:Mi can't decide whether Mn halts}∥.f(i)=‖{n:Mi can't decide whether Mn halts}‖.f(i) = \|\{n: M_i \text{ can't decide...
A côté du milieu universitaire qui est clairement le berceau des théoriciens, je m'interroge sur les métiers industriels liés à l'informatique théorique, ceux qui demandent une formation mathématique pure. À votre santé
Considérons une fonction calculée par un circuit booléen C avec n entrées de taille s ( n ) = p o l y ( n ) sur la base { X O R , A N D , N O T } (avec indegree 2 pour le X O R , A N D portes).FffCCCnnns ( n ) = p o l y ( n )s(n)=poly(n)s(n) = \mathsf{poly}(n){ X O R , A N D , N O T...
Soit C4C4C_4 un cycle à quatre sommets. Pour un graphe arbitraire GGG avec nnn sommets et m arêtes disons m>nn−−√m>nnm>n\sqrt n , combien deC4C4C_4existent? Y a-t-il une limite inférieure pour
Je suis un étudiant diplômé de troisième année dans une université "top 20" qui travaille sur la complexité fine (beaucoup de jeu avec 3-SUM, OV et les conjectures de dureté populaires habituelles). J'ai été assez productif au cours de la dernière année environ et j'ai 3 articles acceptés et 2...
Il est bien connu que le complément de est sans contexte. Mais qu'en est-il du complément de ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Je lis la preuve d' ici et je suis tombé sur un problème technique (pourtant crucial). Je sais que c'est assez spécifique et le contexte est problématique, mais je n'ai pas pu le comprendre moi-même. Aux pages 51 et 55, après avoir présenté les vérificateurs "standard", ils se tournent pour...
Supposons que l'on ait un algorithme randomisé (BPP) UNEAA utilisant rrr bits de caractère aléatoire. Les moyens naturels d'amplifier sa probabilité de réussite à 1 - δ1−δ1-\delta , pour tout δ> 0δ>0\delta>0 choisi , sont Exécutions indépendantes + vote majoritaire: exécutez UNEAA...
Je suis particulièrement intéressé par leur utilisation dans les applications de vérification de modèle. J'ai des réseaux de files d'attente ouverts, fermés et mixtes avec différentes classes de clients par Baskett et al. Avez-vous d'autres suggestions pour lire du matériel?...
Dans un graphe dirigé, , F ⊂ E , si G ∖ F est un DAG (graphe acyclique dirigé), F est appelé un ensemble d'arc de rétroaction. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Si chaque bord est associé à un poids , le problème de jeu d'arc à rétroaction de coût minimum est de trouver un...