Cette question concerne la page 125 du livre "Les automates cellulaires dans les espaces hyperboliques: Volume 2" de Maurice Margenstern, Publisher Archives contemporaines, 2008. http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125 De l'avis de l'auteur, la question P = NP est mal posée car...
Considérez le processus suivant: Il y a nnn bacs disposés de haut en bas. Initialement, chaque bac contient une balle. À chaque étape, nous choisir une balle bbb uniformément au hasard et déplacez toutes les boules du bac contenant bbb vers le bac en dessous. S'il s'agissait déjà du bac le plus...
Supposons que vous ayez deux participants arbitrairement puissants qui ne se font pas confiance. Ils ont accès à l'engagement de bits (par exemple, des enveloppes scellées contenant des données qu'un joueur peut remettre à l'autre mais qui ne peuvent pas être ouvertes jusqu'à ce que le premier...
( MISE À JOUR : une question mieux formulée est posée ici car les commentaires pour la réponse acceptée ci-dessous montrent que cette question n'est pas bien définie) La preuve classique de l'impossibilité du problème d'arrêt dépend de la démonstration d'une contradiction lors de la tentative...
Une fonction f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^* est unidirectionnelle si fff peut être calculé par un algorithme de temps polynomial, mais pour chaque algorithme de temps polynomial randomisé AAA ,
Étant donné un ensemble S de matrices de permutation nxn (qui n'est qu'une petite fraction des n! Matrices de permutation possibles), comment pouvons-nous trouver des sous-ensembles de taille minimale T de S tels que l'ajout des matrices de T a au moins 1 dans chaque position? Je suis intéressé par...
C'est une question dans l'esprit de celle-ci où j'ai répondu qu'il est important de garder une trace de ce que vous avez fait quelque chose, pourquoi vous l'avez fait et ce qui ne fonctionne pas. J'utilise personnellement des ordinateurs portables à cette fin, mais cela présente plusieurs...
On nous donne une famille FF\mathcal{F} de mmm sous-ensembles de {1, ..., n}. Est-il possible de trouver une borne inférieure non triviale sur la complexité de décider si FF\mathcal{F} est une famille Sperner? La borne inférieure triviale est O(nm)O(nm)O(n m) et je soupçonne fortement qu'elle n'est...
Étant donné les points dans R d et une distance l, trouver le plus grand sous-ensemble de ces points de sorte que la distance euclidienne de deux d'entre eux ne dépasse pas l .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll Quelle est la complexité de ce problème? Dans le graphique sur les...
Une question récente a discuté de l'algorithme de programmation dynamique désormais classique pour TSP, dû indépendamment à Bellman et Held-Karp . Il est universellement rapporté que l' algorithme s'exécute en temps . Cependant, comme l'un de mes étudiants l'a récemment souligné, ce temps...
Étant donné deux arbres AVL T1T1T_1 et T2T2T_2 et une valeur trtrt_r telle que ∀x∈T1,∀y∈T2,x<tr<y∀x∈T1,∀y∈T2,x<tr<y\forall x \in T_1, \forall y \in T_2, x < t_r < y , il est facile de construire un nouvel arbre AVL contenant trtrt_r et les valeurs en T1T1T_1 et T2T2T_2 dans le temps...
Soit la complexité de Kolmogorov d'une chaîne x . Existe-t-il une chaîne telle que K ( x x ) < K ( x ) . (Ici x x est la concaténation de x avec lui-même). Une question similaire mais différente a été posée ici , mais le contre-exemple donné dans la réponse à cette question ne fonctionne pas...
sup AO PTsouperUNEOPT\sup\frac{A}{OPT}MjeNMjeNMINUNEUNEAUNEUNEAO PTOPTOPTinf Ω - AΩ - O PTinfΩ-UNEΩ-OPT\inf\frac{\Omega-A}{\Omega-OPT}ΩΩ\Omega il donne le même rapport d'approximation pour des problèmes tels que la couverture minimale des sommets et l'ensemble indépendant maximal qui sont connus...
Il est bien connu que les formules aléatoires -CNF sur n variables avec c n clauses sont insatisfaisantes (c'est-à-dire qu'elles sont des contradictions) avec une probabilité élevée, pour une constante c suffisamment grande . Ainsi, les formules k -CNF aléatoires (pour c assez grand) constituent...
Après avoir travaillé avec 2-3 arbres à doigts pendant un bon moment, j'ai été impressionné par leur vitesse dans la plupart des opérations. Cependant, le seul problème que j'ai rencontré est la surcharge importante associée à la création initiale d'un grand arbre à doigts. Parce que la...
Je me demandais s'il y avait une bonne bibliographie des tentatives d'enquêter sur la conjecture de Collatz comme grammaire formelle? (ou toute autre tentative dans la communauté CS pour faire face à cette classe de phénomènes génératifs et leurs propriétés
Existe-t-il une théorie du langage de programmation décrivant les interfaces de fonctions étrangères (FFI) et les liaisons de plusieurs langages? J'ai posé quelques problèmes d'implémentation sur stackoverflow , qui ne convient pas ici. Mais je voudrais demander du point de vue de ce site et voir...
L'une des choses étonnantes de l'informatique est que l'implémentation physique est en quelque sorte «hors de propos». Les gens ont réussi à construire des ordinateurs à partir de plusieurs substrats différents - relais, tubes à vide, transistors discrets, etc. Les gens pourraient bientôt réussir à...
Le cas des graphiques fortement réguliers est-il le plus difficile à tester GI? où "le plus dur" est utilisé dans un sens "commun", ou "en moyenne", pour ainsi dire. Wolfram MathWorld mentionne quelques "graphiques pathologiquement durs". Que sont-ils? Mon échantillon de 25 paires de graphiques:...
Prenez un graphe orienté où les bords sont décorés d'un nombre naturel. On veut l'ensemble de tous les chemins entre deux sommets et telle sorte que chaque bord successif du chemin soit décoré d'un nombre naturel supérieur au nombre naturel décorant le bord précédent.ggGPPPv1v1v_1v2v2v_2 Une...