J'essaie de résoudre un problème particulier et j'ai pensé que je pourrais le résoudre en utilisant la théorie des automates. Je me demande, quels modèles d'automates ont un confinement décidable en temps polynomial? c'est-à-dire que si vous avez des machines vous pouvez tester si...
Le problème suivant est-il dans PTIME ou coNP-hard: Étant donné deux expressions booléennes et e 2 dans les variables x 1 , … , x n , sans négation (c'est-à-dire que les expressions sont entièrement construites via ∧ et ∨ ). Décidez si e 1 ≡ e 2 , c'est-à-dire qu'ils ont la même valeur pour toutes...
Je souhaite trier un tableau de valeurs entières positives L=v1,…,vnL=v1,…,vnL = v_1, \ldots, v_n en temps linéaire (dans le modèle RAM avec mesure de coût uniforme, c'est-à-dire que les entiers peuvent avoir jusqu'à la taille logarithmique mais les opérations arithmétiques sur eux sont supposées...
Étant donné deux matrices A et B , le problème de décider s'il existe une matrice de permutation P telle que B = P - 1 A P est équivalent à (Isomorphisme graphique). Mais si nous relaxons P pour n'être qu'une matrice inversible, alors quelle est la complexité? Existe-t-il d'autres restrictions sur...
Étant donné une matrice (en supposant ), quel est l'algorithme le plus rapide pour calculer son rang et sa base des colonnes?m × nm×nm \times nm ≥ nm≥nm \ge n Je suis conscient qu'il peut être résolu par intersection matroïde linéaire, ce qui implique un algorithme déterministe temporel et un...
Existe-t-il un algorithme de réarrangement temporel sur place linéaire? C'est l'algorithme que certaines mains particulièrement habiles sont capables d'exécuter: diviser uniformément un tableau d'entrée de taille égale, puis entrelacer les éléments des deux moitiés. Mathworld a une brève page sur...
Considérons le problème # P-complet de compter le nombre de couvertures de sommets d'un graphe donné G=(V,E)G=(V,E)G = (V, E) . Je voudrais savoir s'il y a un résultat montrant comment la dureté d'un tel problème varie avec un paramètre de GGG (par exemple, d=|E||V|d=|E||V|d = \frac{|E|}{|V|}). Ma...
Je recherche des informations sur la complexité de calcul de la multiplication matricielle des matrices rectangulaires. Wikipedia indique que la complexité de la multiplication de par B ∈ R n × p est O ( m n p ) (multiplication des manuels scolaires).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times...
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...
J'avais fait quelques recherches à ce sujet mais je n'ai pas pu trouver de réponse dans les deux cas. Huck y répondit pleinement. Merci
Connaît-on des résultats qui excluent l'existence de structures de données «trop belles pour être vraies»? Par exemple: peut-on ajouter des fonctionnalités et J o i n à une structure de données de maintenance de commande (voir Dietz et Sleator STOC '87 ) tout en obtenant des opérations de temps O (...
Il est bien connu que la complexité de distinguer une pièce biaisée une pièce équitable est θ ( ϵ - 2 ) . Y a-t-il des résultats pour distinguer une pièce p d' une pièce p + ϵ ? Je peux voir que pour le cas particulier de p = 0 , la complexité sera ϵ - 1 . J'ai le pressentiment que la complexité...
On dit qu'une fonction f:N→Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} est constructible dans le temps , s'il existe une machine de Turing déterministe multi-bandes MMM qui sur toutes les entrées de longueur nnn fait au plus f(n)f(n)f(n) pas et pour chaque nnn il existe une entrée de longueur nnn sur...
L'élimination gaussienne rend le déterminant d'une matrice polynomiale temps calculable. La réduction de la complexité dans le calcul du déterminant, qui est autrement la somme de termes exponentiels, est due à la présence de signes négatifs alternatifs (dont le manque rend le calcul permanent est...
Connaissez-vous des problèmes (de préférence au moins assez bien connus) où, pour une taille de problème pratique , un algorithme exponentiel s'exécute beaucoup plus rapidement qu'un homologue polynomial le plus connu. Par exemple, supposons qu'un problème ait une taille pratique * de et qu'il...
Ce que j'appelle compter, c'est le problème qui consiste à trouver le nombre de solutions à une fonction. Plus précisément, étant donné une fonction (pas nécessairement une boîte noire), approximative .f:N→{0,1}f:N→{0,1}f:N\to \{0,1\}# { x ∈ N∣ f( x ) = 1 } = | F- 1( 1 )...
Fixer un problème de recherche NP-complet, par exemple le formulaire de recherche de SAT. La recherche de Levin fournit un algorithme L pour résoudre X qui est optimal dans un certain sens. Plus précisément, l'algorithme est "Exécute tous les programmes P possibles en queue d'aronde sur l'entrée x...
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...
Existe-t-il des problèmes décidables tels que pour aucun algorithme qui résout le problème, nous pouvons donner une limite de temps en fonction de la longueur n de l'instance d'entrée? Je suis arrivé à cette question parce que je pensais à ce qui suit: Supposons que nous ayons un problème...
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...