Considérez le problème de test d'appartenance au sous-groupe abelian suivant . Contributions: Un groupe abélien fini G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} avec arbitrairement grand .didid_i Un générateur de jeu d'un sous - groupe...
Cette question est inspirée d'une question existante sur la possibilité de simuler une pile à l'aide de deux files d'attente en temps amorti par opération de pile. La réponse semble inconnue. Voici une question plus spécifique, correspondant au cas particulier dans lequel toutes les opérations PUSH...
Dans la théorie de la complexité, la définition de la complexité du temps et de l'espace fait référence à une machine de Turing universelle: resp. le nombre d'étapes avant de s'arrêter et le nombre de cellules sur la bande touchées. Compte tenu de la thèse de Church-Turing, il devrait également...
Dans l'article de Stephen Cook sur le problème P vs NP [1], il déclare ce qui suit [2]: Thèse de faisabilité: Un problème naturel a un algorithme réalisable s'il a un algorithme polynomial. Ma question est, que veut-il dire exactement (ou en général, qu'est-ce que l'on entend) par "un problème...
Je cherche un algorithme efficace pour le problème: Entrée : l'entier positif (stocké sous forme de bits) pour un entier . n ≥ 03n3n3^nn ≥ 0n≥0n \geq 0 Sortie : Le nombre .nnn Question : Peut-on calculer partir des bits de en temps ?3 n O ( n )nnn3n3n3^nO (n )O(n)O(n) Il s'agit d'une question...
Merlin, qui a des ressources informatiques illimitées, veut convaincre Arthur que m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\ p\text{ prime}}p^k pour (N,m,k)(N,m,k)(N,m,k) avec k=O(logN)k=O(logN)k=O(\log N) et m=O(N).m=O(N).m=O(N). Le calcul simple de cette somme (exponentiation modulaire...
Quelle est la complexité du problème suivant ( P? NP-hard?):∈∈\in Entrée: un graphe acyclique dirigé , un ensemble d'arêtes arrières , et deux nœuds distincts et .E ′ ⊂ V × V s tD = ( V, E)D=(V,E)D=(V,E)E′⊂ V× VE′⊂V×VE'\subset V\times Vsssttt Question: Soit le graphe formé en ajoutant à les bords...
Le théorème de Borsuk-Ulam dit que pour chaque fonction impaire continue ggg d'une sphère n dans un espace n euclidien, il y a un point X0x0x_0 tel que g( x0) = 0g(X0)=0g(x_0)=0 . Simmons et Su (2002) décrivent une méthode pour approximer le point X0X0x_0 utilisant le lemme de Tucker . Cependant,...
Étant donné un circuit booléen sur variables (qui utilise uniquement les portes NON, ET et OU), quelle est la manière la plus efficace d'extraire la formule booléenne représentée par le circuit? Existe-t-il un algorithme de polytime pour ce
Je jouais avec la question très intéressante et toujours ouverte " Alphabet of single-tape Turing machine " (par Emanuele Viola) et j'ai trouvé la langue suivante: L = { x ∈ { 0 , 1 }n st | x | = n = 2m et c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1
Pour un graphe non orienté et un ensemble de sommets, ce qui est l'algorithme connu asymptotiquement le plus rapide pour trouver un chemin simple contenant tous les éléments de . Et si nous voulons que le chemin soit le plus court possible?S
Supposons que j'ai deux listes d'entiers positifs de manitude bornée et que je prenne le produit de tous les éléments de chaque liste. Quelle est la meilleure façon de déterminer quel produit est plus grand? Bien sûr, je peux simplement calculer chaque produit, mais j'espère qu'il existe une...
En un mot, les théorèmes de la hiérarchie du temps disent qu'une machine de Turing peut résoudre plus de problèmes si elle a plus de temps pour le calcul. En détail pour TM déterministe et fonctions constructibles dans le temps avec c'est et pour TM non déterministe et fonctions constructibles dans...
Je suis confus. Je veux prouver que le problème du tri d'une matrice nnn par nnn c'est-à-dire que les lignes et les colonnes sont en ordre croissant est Ω(n2logn)Ω(n2logn)\Omega(n^2\log n) . Je continue en supposant que cela peut être fait plus rapidement que n2Journalnn2lognn^2\log n et j'essaie...
Je suis intéressé par des algorithmes efficaces pour l'intersection DFA pour des cas spéciaux. A savoir, lorsque les DFA se croisent obéissent à une certaine structure et / ou opèrent sur un alphabet limité. Y a-t-il une source où je peux trouver des algorithmes de tels cas? Afin de ne pas rendre...
Il s'agit d'une version spécialisée d'une question précédente: Complexité de la recherche de la composition par matrice d'une matrice . Pour les matrices symétriques NxN, il est connu que le temps O (N ^ 3) suffit pour calculer la décomposition propre. La question est: pouvons-nous atteindre une...
Nous avons un problème et nous avons trouvé un algorithme qui semble être 2-nexptime. Je voudrais trouver des problèmes connus de 2-nexptime-complete afin de trouver une borne inférieure. J'ai trouvé dans la littérature principalement deux de ces problèmes: si PCP comme solution de taille...
Pour de nombreux problèmes, l'algorithme avec la meilleure complexité asymptotique a un très grand facteur constant qui est caché par une grande notation O. Cela se produit dans la multiplication matricielle, la multiplication d'entiers (en particulier, le récent algorithme de multiplication...