Soit une matrice A avec des entrées rationnelles. Quelle est la complexité de vérifier que A est diagonalisable?n × nn×nn\times nUNEUNEAUNEUNEA Je soupçonne que cela peut être fait en P, mais je ne connais aucune référence. Cependant, une question plus intéressante est: existe-t-il une meilleure...
De manière informelle, les fonctions unidirectionnelles sont définies par rapport aux algorithmes PTIME. Ils sont calculables en temps polynomial mais non inversibles en temps polynomial moyen. L'existence de telles fonctions est un problème ouvert important en informatique théorique. Je...
Soit une fonction booléenne de n variables booléennes. Soit g ( x ) = T ϵ ( f ) ( x ) la valeur attendue de f ( y ) lorsque y est obtenu à partir de x en inversant chaque coordonnée avec la probabilité ϵ / 2 .fffnnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)f(y)f(y)f(y)yyyxxxϵ/2ϵ/2\epsilon/2...
Si je comprends bien, une preuve que P = NP ou P ≠ NP devrait être non relativisable (comme dans les oracles de la théorie de la récursivité). Cependant, presque toutes les preuves semblent être relativisables. Quels sont les bons exemples de preuves non relativisables, du type d'une preuve P = NP...
Supposons P NP.≠≠\ne Le théorème de Ladner dit qu'il existe des problèmes NP intermédiaires (problèmes dans NP qui ne sont ni dans P ni NP-Complete). J'ai trouvé en ligne des références voilées qui suggèrent (je pense) qu'il existe de nombreux "niveaux" de langues mutuellement réductibles au sein...
Les éléments suivants peuvent-ils tous tenir simultanément? LsLsL_s est contenu dansLs+1Ls+1L_{s+1} pour tous les entiers positifssss . { 0 , 1 }L=⋃sLsL=⋃sLsL = \bigcup_s L_s est la langue de tous les mots finis sur .{0,1}{0,1}\{0,1\} Il y a une classe de complexité et une notion de réduction...
Une question récente (voir les conséquences de NP = PSPACE ) a demandé des conséquences "désagréables" de . Les réponses liste assez peu de conséquences de l' effondrement, y compris N P = c o N P et d' autres, en fournissant beaucoup de raisons de croire N P ≠ P S P A C E...
Soit la fonction majoritaire, c'est-à-dire f ( x ) = 1 si et seulement si ∑ n i = 1 x i > n / 2 . Je me demandais s'il y avait une preuve simple du fait suivant (par «simple», je veux dire ne pas compter sur la méthode probabiliste comme Valiant 84 ou sur les réseaux de tri; fournissant de...
J'étudie récemment le modèle de calcul BSS (cf. par exemple Complexité et calcul réel; Blum, Cucker, Shub, Smale.) Pour les réels , on montre que, étant donné un système de polynômes f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] , l'existence de zéros est N P R -complète. Cependant, je me demande si ces f...
Le titre est un peu trompeur: mais j'espère que la question n'est pas: Grønlund et nouveau résultat Pettie montrant que 3sum a seulement la complexité de l' arbre de décision m'a demander:O ( n3 / 2)O(n3/2)O(n^{3/2}) Y a-t-il un exemple simple d'un problème avec une complexité d'arbre de décision...
J'ai une réduction du problème de partition suivant à un certain problème de planification: Entrée: Une liste une1⩽ ⋯ ⩽ anune1⩽⋯⩽unena_1\leqslant\cdots\leqslant a_n d'entiers positifs dans l'ordre non décroissant. Question: Existe-t-il un vecteur ( x1, … , Xn) ∈ { - 1 , 1...
Contexte: La complexité de l'arbre de décision ou la complexité des requêtes est un modèle de calcul simple défini comme suit. Soit F: { 0 , 1 }n→ { 0 , 1 }F:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\} une fonction booléenne. La complexité de requête déterministe de FFf , notée D ( f)ré(F)D(f) , est le...
Étant donné un algorithme fonctionnant au temps , nous pouvons le convertir en une famille de circuits uniformes "triviaux" pour le même problème de taille au plus ≈ t ( n ) log t ( n ) .t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) D'un autre côté, il se pourrait que nous ayons des...
Dans le problème d'extensibilité, on nous donne une partie de la solution et nous voulons décider si nous pouvons l'étendre à une solution complète. Certains problèmes d'extensibilité peuvent être résolus efficacement tandis que d'autres problèmes d'extensibilité transforment un problème facile en...
La hiérarchie est une hiérarchie de classes de complexité en complexité paramétrée, voir le Complexity Zoo pour les définitions. Une définition alternative définit utilisant la définissabilité pondérée de Fagin pour les logique du premier ordre, voir le manuel de Flum et Grohe...
Étant donné un groupe de permutations sur [ n ] = { 1 , ⋯ , n } , et deux vecteurs u , v ∈ Γ n où Γ est un alphabet fini qui n'est pas tout à fait pertinent ici, la question est de savoir s'il existe des π ∈ G tel que π ( u ) = v où π ( u ) signifie appliquer la permutation π sur u de manière...
En écrivant un petit post sur la complexité des jeux vidéo Nibbler et Snake ; J'ai trouvé que les deux peuvent être modélisés comme des problèmes de reconfiguration sur les graphes planaires; et il semble peu probable que de tels problèmes n'aient pas été bien étudiés dans le domaine de la...
Sait-on quelque chose sur la deuxième plus petite coupe - t dans un réseau de flux? Ou, plus généralement, à propos de ce problème:sssttt Entrée: Un réseau et un nombre k , tous en binaire. Sortie: A k e plus petit s - t coupé.NNNkkkkkksssttt Une ème plus petite coupe s - t ( S , T ) est toute...
P / poly est la classe de problèmes de décision pouvant être résolus par une famille de circuits booléens de taille polynomiale. Il peut également être défini comme une machine de Turing à temps polynomial qui reçoit une chaîne de conseils de taille polynomiale en n et basée uniquement sur la...
Considérons le problème où on nous donne en entrée un graphe acyclique dirigé , une fonction d'étiquetage λ de V vers un ensemble L avec un ordre total < L (par exemple, les entiers), et où on nous demande de calculer le plus petit tri topologique lexicographiquement de G en termes de λ . Plus...