Je veux en savoir plus sur les algorithmes algébriques et la complexité de la théorie. Je m'intéresse en particulier au PIT. Existe-t-il un ensemble de notes de cours, de livres, d'articles et d'enquêtes pour les étudiants qui ont lu un manuel standard sur la théorie comme le livre de Sipser ou le...
On peut parler de la largeur d' arbre d'un circuit booléen, la définissant comme la largeur d'arbre du graphe "moralisé" sur les fils (sommets) obtenu comme suit: connectez les fils uneunea et bbb chaque fois que bbb est la sortie d'une porte ayant uneunea entrée (ou vice versa); connectez les fils...
Un automate Xor non déterministe (NXA) est syntaxiquement un NFA, mais un mot est dit accepté par NXA s'il a un nombre impair de chemins d'acceptation (au lieu d'au moins un chemin d'acceptation dans le cas NFA). Il est facile de voir que pour un langage régulier fini , il existe un NFA minimal qui...
Je me suis récemment intéressé au problème général de l'optimisation de l'utilisation de la mémoire dans une situation où il y a plus d'un type de mémoire disponible, et il y a un compromis entre la capacité d'un segment de mémoire donné et la vitesse d'accès. L'exemple familier est un programme...
Je me demande s'il existe une version limitée du calcul du concept d'équilibre de Nash, quelque chose dans le sens suivant. Imaginez une sorte de jeu d'information parfait à deux joueurs qui se joue sur un plateau , et qui est complexe dans le sens où un jeu optimal est dur-EXPTIME. Supposons...
Le théorème d'incomplétude de Chaitin dit qu'aucune théorie suffisamment forte de l'arithmétique ne peut prouver où est la complexité de Kolmogorov de la chaîne et est une constante suffisamment grande. est suffisamment grand s'il est supérieur à la taille en bits d'une machine de vérification...
Je lisais l'article de wikipedia sur le problème des huit reines. Il est indiqué qu'il n'existe pas de formule connue pour le nombre exact de solutions. Après quelques recherches, j'ai trouvé un article intitulé "Sur la dureté des problèmes de comptage des mappings complets". Dans cet article, il y...
La plupart d'entre nous connaissent - ou du moins ont entendu parler - l'entropie de Shannon d'une variable aléatoire, H(X)=−E[logp(X)]H(X)=−E[logp(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] , et toutes les mesures théoriques de l'information connexes telles que l'entropie relative, informations...
Je recherche des exemples de résultats qui vont à l'encontre de l'intuition des gens pour une conférence grand public. Des résultats qui, s'ils étaient demandés à des non-experts "qu'est-ce que votre intuition vous dit?", Presque tous auraient tort. L'énoncé des résultats devrait être facilement...
Nous considérons les DAG (graphes acycliques dirigés) avec un nœud source sss et un nœud cible ; les arêtes parallèles joignant la même paire de sommets sont autorisées. A - coupe est un ensemble d'arêtes dont le retrait détruit toutes - chemins plus longs que ; des chemins - courts ainsi que de...
Basé sur le manuel Introduction to Algorithms , l'exactitude d'un algorithme gourmand nécessite qu'un problème ait deux propriétés: propriété de choix gourmande sous-structure optimale Il est facile de trouver des contre-exemples pour lesquels une solution gourmande échoue en raison du manque de la...
Supposons que nous connectons les points de V=Z2V=Z2V = \mathbb{Z}^2 utilisant l'ensemble des bords non orientés EEE telle sorte que (i,j)(i,j)(i, j) soit connecté à (i+1,j+1)(i+1,j+1)(i + 1, j + 1) , ou (i+1,j)(i+1,j)(i + 1, j) soit connecté à (i,j+1)(i,j+1)(i, j + 1) , indépendamment et...
Razborov a prouvé que la correspondance de fonction monotone n'est pas en mP . Mais peut-on calculer l'appariement en utilisant un circuit de taille polynomiale avec quelques négations? Existe-t-il un circuit P / poly avec des négations qui calcule la correspondance? Quel est le compromis entre le...
Considérons un vecteur de variables et un ensemble de contraintes linéaires spécifiées par .X⃗ X→\vec{x}A x⃗ ≤ bUNEX→≤bA\vec{x}\leq b En outre, considérons deux polytopes
Problème: étant donné représenté par un circuit booléen, générer un uniformément aléatoire tel que (ou sortie si un tel n'existe pas). ϕ : { 0 , 1 }n→ { 0 , 1 }ϕ:{0,1}n→{0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }nX∈{0,1}nx \in \{0,1\}^nϕ ( x ) = 1ϕ(X)=1\phi(x)=1⊥⊥\perpXXx Clairement, ce...
Le temps constant est la complexité absolue la plus basse. On peut se demander: y a-t-il quelque chose de non trivial qui peut être calculé en temps constant? Si nous nous en tenons au modèle de la machine de Turing, alors peu de choses peuvent être faites, car la réponse ne peut dépendre que d'un...
Les relations logiques pour les langages imprédicatifs comme le système F semblent s'appuyer de manière critique sur l'imprédicativité de la logique ambiante. Plus précisément, l'interprétation du forall-type sera définie en termes de toutes les relations typées. Dans un système imprédicatif (comme...
Je suis un ingénieur logiciel assez compétent, mais je ne connais pas beaucoup la théorie. Je veux en savoir plus sur la théorie. Les sujets particuliers qui m'intéressent sont: la complexité informatique, les langages formels et la théorie des types. Mais je ne sais pas trop comment commencer à...
Pour tout langage arbitraire NP complet, existe-t-il toujours un surensemble de polytimes dont le complément est également infini? Une version triviale qui ne stipule pas que le sur-ensemble a un complément infini a été demandée à /cs//q/50123/42961 Aux fins de cette question, vous pouvez supposer...
Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReg\mathsf{Reg}TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg}Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0}NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0}Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} Y a-t-il un...