Il est connu que minimiser la taille d'une expression régulière est PSPACE-complete même si nous avons un DFA comme spécification du langage . Quels sont les résultats si la langue est finie? On peut considérer ce problème dans deux modèles: L'entrée correspond à toutes les chaînes du langage, et...
J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile. Somme Sous - ensemble: Étant donné X= { x1, . . . , xn}X={X1,...,Xn}X = \{x_1,...,x_n\}...
Il y a eu un travail fantastique sur le permanent en cours au cours des deux dernières décennies et je m'interroge depuis un moment sur la possibilité d'un algorithme Smooth P pour le permanent des matrices non négatives. Il y a bien sûr le fameux algorithme JSV mais c'est un fpras. En pensant à...
On me donne en entrée un DAG de sommets où chaque sommet est en outre étiqueté avec quelques .n x S ( x ) ⊆ { 1 , … , n }GGGnnnxxxS(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Une sorte topologique de est une bijection des sommets de vers telle sorte que pour tout , , s'il y a un chemin...
Existe-t-il un moyen naturel de comprendre l'essence de la sémantique relationnelle pour le polymorphisme paramétrique? Je viens de commencer à lire sur la notion de paramétrie relationnelle, à la "Types, abstraction et polymorphisme paramétrique" de John Reynolds, et j'ai du mal à comprendre...
Il existe des études sur les algorithmes d'approximation pour les problèmes NP complets en temps polynomial et les algorithmes exacts en temps exponentiel. Existe-t-il des études sur les algorithmes d'approximation des problèmes NP complets en temps sous-exponentiel de forme où δ 2 ∈ ( 0 , 1 )...
Ceci est écrit dans l'entrée wiki de Symbolic Execution , mais je ne trouve aucune référence pour cela. Quelqu'un peut-il me montrer un pointeur? Je vous
Les efforts de vérification du compilateur se résument souvent à prouver que le compilateur est complètement abstrait: qu'il préserve et reflète les équivalences (contextuelles). Au lieu de fournir des preuves d'abstraction complètes, certains travaux récents de vérification du compilateur (basés...
L'isomorphisme graphique ( ) est un bon candidat pour un problème intermédiaire . problèmes intermédiaires existent sauf si . Je recherche un problème naturel difficile pour sous réduction de Karp (Un problème graphique tel que ).GIGIGINPNPNPNPNPNPP=NPP=NPP=NPGIGIGIXXXGI<mpXGI<pmXGI...
Une façon de montrer que la vérification de la faisabilité d'un système linéaire d'inégalités est aussi difficile que la programmation linéaire passe par la réduction donnée par la méthode ellipsoïde. Un moyen encore plus simple consiste à deviner la solution optimale et à l'introduire comme...
Quand on nous donne une décomposition arborescente d'un graphe de largeur , il y a plusieurs façons de le rendre "agréable". En particulier, il est connu qu'il est possible de le transformer en une décomposition d'arbre où l'arbre est binaire et sa hauteur est . Ceci peut être réalisé tout en...
Nous disons qu'une Turing Machine est mortelle si M s'arrête pour chaque configuration de départ (en particulier, le contenu de la bande et l'état initial peuvent être arbitraires). Chaque langage récursif est-il reconnu par une machine de Turing mortelle? (c'est-à-dire s'il y a une MT qui accepte...
Il existe de nombreuses situations où une "preuve" randomisée est beaucoup plus facile qu'une preuve déterministe, l'exemple canonique étant le test d'identité polynomiale. Question : Existe-t-il des "théorèmes" mathématiques naturels où une preuve randomisée est connue mais pas une preuve...
Question courte. Quelle est la puissance de calcul des circuits "quantiques", si nous autorisons des portes non unitaires (mais toujours inversibles) et exigons que la sortie donne la réponse correcte avec certitude? Cette question concerne en quelque sorte ce qui arrive à la classe lorsque vous...
Je voudrais demander des suggestions de bons textes qui introduisent la complexité du circuit. Des indications sur les avancées récentes et les problèmes ouverts dans ce domaine seraient également
L'un des problèmes ouverts intéressants concernant les DFA est répertorié dans Existe-t-il des problèmes ouverts concernant les DFA? est la taille d'un DFA requis pour séparer deux chaînes de longueur . Je suis curieux de savoir s'il existe des résultats sur la capacité d'un DFA aléatoire à séparer...
Plutôt que des preuves empiriques, par quels principes formels avons-nous prouvé que l'informatique quantique sera plus rapide que l'informatique traditionnelle /
Que se passe-t-il si nous définissons telle sorte qu'au lieu d'un circuit Turing-machine / polysize polytime, une machine Turing espace journal ou un circuit code le problème?P P A DPPAD{\bf PPAD} A C 0AC0{\bf AC^0} Donner récemment des algorithmes plus rapides pour la satisfiabilité des circuits...
Chaque circuit arithmétique monotone , c'est-à-dire un circuit { + , × }{+,×}\{+,\times\} , calcule un polynôme multivarié avec des coefficients entiers non négatifs. Étant donné un polynôme , le circuitf ( x 1 , … , x n )F( x1, … , Xn)F(X1,…,Xn)F(x_1,\ldots,x_n)F( x1, … ,...
FewP est la classe des problèmes avec polynôme lié au nombre de solutions (dans la taille d'entrée). On ne connaît pas problème -complete dans . Je voudrais savoir jusqu'où nous pouvons étendre cette observation.N P f e w PNPNPNPNPNPNPfewPFewPfewP Existe-t-il un problème naturel de complet avec une...