Le kkk -ième polynôme symétrique élémentaire est la somme de tous produits de variables distinctes. Je m'intéresse à la complexité du circuit arithmétique monotone de ce polynôme. Un algorithme de programmation dynamique simple (ainsi que la figure 1 ci-dessous) donne un circuit avec des portes...
Soit la famille de toutes les langues sur satisfaisant la propriété de pompage des langues régulières. A savoir: pour chaque , il y a un st chaque mot , peut s'écrire sous la forme w = xyz où: 1. | y |> 0 , 2. | xy | \ le N , 3. xy ^ iz \ in L pour tout i \ ge 0 . Σ L ∈ L N ∈ N w ∈ L | w | >...
Le non-déterminisme peut-il accélérer le calcul déterministe? Si oui, combien? En accélérant le calcul déterministe par le non-déterminisme, j'entends les résultats de la forme: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Par exemple quelque chose comme...
Soit L⊆X∗L⊆X∗L \subseteq X^{\ast} un langage, puis nous définissons la congruence syntaxique comme u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈Lu∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L et le quotient monoïde est appelé monoïde syntaxique de...
Existe-t-il des problèmes intéressants dans mais non connus dans ? Dans l'article «Une taxonomie des problèmes avec les algorithmes parallèles rapides», Cook mentionne que MIS était connu pour être uniquement dans mais cela a depuis été ramené à . Je me demande s'il y a d'autres problèmes avec les...
Qu'est-ce qui empêche ghc de traduire Haskell en un langage de programmation concaténatif tel que la logique combinatoire, puis d'utiliser simplement l'allocation de pile pour tout? Selon Wikipedia, la traduction du calcul lambda à la logique combinatoire est triviale, et les langages de...
Y a-t-il une "belle" hiérarchie (peut-être finie) à l'intérieur de la classe des langues régulières ? Par gentil ici, les classes de chaque hiérarchie capturent différentes expressivités / puissance / complexité. De plus, l'appartenance à chaque classe est "joliment" démontrée par certains éléments...
J'ai pensé à ces questions: Existe-t-il un calcul lambda typé cohérent et complet de Turing? /cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent et il y a déjà quelques questions difficiles à répondre dans le cadre non typé ! Plus précisément, je suis curieux de savoir si nous...
Pour une théorie des types, par cohérence, je veux dire qu'elle a un type qui n'est pas habité. De la forte normalisation du cube lambda, il s'ensuit que le système FFF et le système FωFωF_\omega sont cohérents. Les types inductifs MLTT + ont également une preuve de normalisation. Cependant,...
Y at - il eu des travaux visant à trouver le nombre minimum d'opérations arithmétiques élémentaires nécessaires pour calculer le déterminant d'un par matrice pour les petites et fixe ? Par exemple, .n n n =
Je lisais récemment un très bon article de Valiant et Vazirani qui montre que si NP≠RPNP≠RP\mathbf{NP \neq RP} , il ne peut pas y avoir d'algorithme efficace pour résoudre SAT même sous la promesse qu'il est insatisfaisant ou qu'il a une solution unique. Montrant ainsi que SAT n'admet pas...
La sémantique d'un grand sous-ensemble d'OCaml, appelé OCamllight , a été formalisée dans HOL par Owens il y a plusieurs années. Plus récemment, une sémantique théorique de type d'un plus petit sous-ensemble d'OCaml a été implémentée dans Nuprl par Kreitz, Hayden et Hickey . Y a-t-il un...
Existe-t-il , un langage NP ou P-complet qui a une famille de groupes de symétrie G n (ou groupoïde , mais alors les questions algorithmiques deviennent plus ouvertes) agissant (en temps polynomial) sur des ensembles L n = { l ∈ L ∣ | l | = n } tel qu'il y ait peu d'orbites, ie tel que | L n / G n...
Comme dans cette question, je suis intéressé par le problème vs / pour les circuits tropicaux et (\ min, +) . Cette question se réduit à montrer les limites supérieures de la dimension VC des polynômes sur les semirings tropicaux (voir le théorème 2 ci-dessous).
Quelle est la complexité du problème suivant? Entrée : unchemin hamiltonienen K nHHHKnKnK_n un sous-ensemble de paires de sommetsR⊆[n]2R⊆[n]2R \subseteq [n]^2 un entier positif kkk Requête : existe-t-il un correspondant tel que pour chaque , ? (où G = ( [ n ] , M ∪ H ) )MMM(v,u)∈R(v,u)∈R(v,u) \in...
Soit la fonction qui mappe un circuit s- porte C sur n bits et une chaîne de n bits x à C ( x ) . Supposons que les circuits sont codés comme une séquence acyclique d'affectations k : = g ( i , j ) où i , j , k sont des étiquettes de fils.C i r c u i t E v a ls ,
Compte tenu des sujets abordés lors d'une conférence comme le STOC, des chercheurs en algorithmes ou en complexité utilisent-ils activement COQ ou Isabelle? Si oui, comment l'utilisent-ils dans leurs recherches? Je suppose que la plupart des gens n'utiliseraient pas de tels outils car les preuves...
Dans le chapitre 1 et l'annexe A du livre Hott , plusieurs familles de types primitifs sont présentées (types d'univers, types de fonctions dépendantes, types de paires dépendantes, types de coproduits, type vide, type d'unité, type de nombre naturel et types d'identité) pour former la base pour la...
Considérez le modèle de circuit monotone simple suivant: chaque porte est juste un OU binaire. Quelle est la complexité d'une fonction f ( x ) = A xf(x)=Axf(x)=Ax où AAA est une matrice booléenne n × nn×nn \times n avec O ( n )O(n)O(n) 0? Peut-il être calculé par des circuits OR de taille linéaire?...
Une langue est en s'il existe une machine de Turing de l'espace de log qui décide de la langue avec une quantité polynomiale de conseils.L/polyL/polyL/poly Voir ici pour plus d'informations: https://en.wikipedia.org/wiki/L/poly Question Quelles sont les conséquences de ?P⊆L/polyP⊆L/polyP \subseteq...