Existe-t-il un système similaire au calcul lambda à forte normalisation, sans qu'il soit nécessaire d'ajouter un système de type
Le fœtus, si vous n'en avez pas entendu parler, peut être lu ici . Il utilise un système de «matrices d'appel» et de «graphiques d'appel» pour trouver tous les «comportements de récursivité» des appels récursifs dans une fonction. Pour montrer qu'une fonction se termine, cela montre que tous les...
Je souhaite savoir comment utiliser les concepts de limites et de colimites pour modéliser des problèmes dans la vie de tous les jours? Quelqu'un pourrait-il peut-être fournir des exemples d'ingénierie (logicielle)? Ou décrire intuitivement en général pour quels types de problèmes de modélisation...
Supposons que j'ai des ensembles avec des éléments pris parmi les r possibles. Chaque ensemble est de taille n ( n < r ), où les ensembles peuvent se chevaucher. Je veux déterminer si les deux problèmes suivants sont NP-complets ou non:PPPrrrnnnn <
J'ai une question naïve: existe-t-il une machine de Turing dont la terminaison est vraie mais non démontrable par aucune théorie naturelle, cohérente et finement axiomatisable? Je demande une simple preuve d'existence plutôt qu'un exemple spécifique. Cela pourrait avoir un lien avec l'analyse...
Quelles sont certaines des meilleures sources (livres et articles) pour motiver et apprendre la complexité de la communication par elle-même et en relation avec sa relation avec la théorie de la complexité
La vérification de la transitivité d'un digraphe n'est-elle pas plus facile que (en termes de complexité asymptotique) de prendre la fermeture transitive du digraphe? Connaissons-nous mieux une borne inférieure que pour déterminer si un digraphe est transitif ou non?Ω (
Il y a eu quelques questions ( 1 , 2 , 3 ) sur l'achèvement transitif ici qui m'ont fait penser si quelque chose comme ça était possible: Supposons que nous obtenions un graphe orienté en entrée et que nous souhaitions répondre aux requêtes de type " ?", C'est-à-dire demander s'il existe une arête...
Dans le problème des cliques plantées, il faut récupérer une -clique plantée dans un graphe aléatoire Erdos-Renyi G ( n , p ) . Cela a surtout été examiné pour p = 1kkkG ( n , p )G(n,p)G(n,p) , auquel cas il est connu pour être soluble dans le temps polynomial sik>√p = 12p=12p=\frac{1}{2} et...
La plupart des systèmes typés dépendants ont des conditions de positivité strictes pour les types inductifs. Quelqu'un connaît-il un exemple où la violation de la condition entraîne une incohérence dans le
Considérons le problème classique # P-complet # 3SAT, c'est-à-dire de compter le nombre d'évaluations pour rendre un 3CNF avec variables satisfaisable. Je m'intéresse à l' approximabilité additive . De toute évidence, il existe un algorithme trivial pour obtenir une erreur de , mais si , est-il...
Je veux diviser un ensemble de points en deux sous-ensembles de taille égale de sorte que la somme des carrés intra-cluster soit minimisée. Nous pouvons supposer que les points sont dans l'espace euclidien à deux dimensions. J'espère quelque chose de plus rapide qu'un algorithme de clustering...
Un homomorphisme d'un graphe à un graphe est un mappage de à tel que si et sont adjacents dans alors et sont adjacents dans . Un endomorphisme d'un graphe est un homomorphisme de à lui-même; il est sans virgule fixe s'il n'y a pas de tel que et il n'est pas trivial si ce n'est...
Quel est le meilleur résultat pour le nombre de portes dans un circuit multipliant deux entiers de n bits? La méthode évidente génère des portes . Il existe de meilleures approches avec les portes et .θ ( n log n log log n ) θ ( n log n 2 log ∗ ( n ) )θ ( n2)θ(n2)\theta(n^2)θ ( n logn...
Disons que nous avons une fonction booléenne et que nous appliquons une restriction aléatoire δ sur f . De plus, disons que l'arbre de décision T qui calcule f se réduit à la taille O ( 1 ) en raison de la restriction aléatoire. Est-ce à dire que f a une influence totale très faible?F: { - 1 , 1...
Soit un polynôme donné par un circuit arithmétique C de taille s . Étant donné C comme entrée, existe-t-il un algorithme déterministe pour vérifier si tous les facteurs irréductibles de f dans Q [ x 1 , x 2 , … , x n ] sont des formes linéaires? Sur une note connexe, étant donné une forme linéaire...
Quel est le rapport entre les CFG ambigus et tous les CFG ? Étant donné que les deux ensembles sont infiniment dénombrables, le rapport n'est pas bien défini. Mais qu'en est-il de la densité asymptotique : limn↦∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG...
Je m'excuse, c'est une question un peu "douce". La théorie de l'information n'a pas de concept de complexité informatique. Par exemple, une instance de SAT ou une instance de SAT plus un bit indiquant la satisfiabilité transportent la même quantité d'informations. Existe-t-il un moyen de formaliser...
Que sait-on de la complexité de la résolution d'un système d'équations linéaires sur un corps fini? Je sais qu'il existe un algorithme (Gauss) qui calcule une solution et que pour les systèmes clairsemés, il existe des algorithmes encore meilleurs. Cependant, je me demandais s'il y avait une...
Soit ré: { 0 , 1 }k× { 0 , 1 }k→ Rd:{0,1}k×{0,1}k→Rd:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R} une fonction que nous appelons la fonction de similarité . Des exemples de fonctions de similitude sont la distance cosinus, la norme , la distance de Hamming, la similitude Jaccard, etc.l2l2l_2...