Étant donné une énorme base de données de mots autorisés (triés par ordre alphabétique) et un mot, recherchez le mot de la base de données le plus proche du mot donné en termes de distance de Levenshtein. L'approche naïve consiste, bien entendu, à simplement calculer la distance de levenshtein...
La conjecture de reconstruction dit que les graphes (avec au moins trois sommets) sont déterminés uniquement par leurs sous-graphes supprimés par les sommets. Cette conjecture a cinq décennies. En recherchant dans la littérature pertinente, j'ai trouvé que les classes de graphiques suivantes sont...
Edit: j'ai d'abord mal formulé ma contrainte (2), elle est maintenant corrigée. J'ai également ajouté plus d'informations et d'exemples. Avec certains collègues, étudiant une autre question algorithmique, nous avons pu réduire notre problème au problème intéressant suivant, mais nous n'avons pas pu...
La théorie de la complexité, à travers des concepts tels que la complétude NP, fait la distinction entre les problèmes de calcul qui ont des solutions relativement efficaces et ceux qui sont insolubles. La complexité "fine" vise à affiner cette distinction qualitative en un guide quantitatif quant...
J'essaie actuellement de trouver des problèmes EXPSPACE-complets (principalement pour trouver l'inspiration pour une réduction), et je suis surpris par le petit nombre de résultats à venir. Jusqu'à présent, je les ai trouvés et j'ai du mal à élargir la liste: universalité (ou autres propriétés) des...
J'ai lu dans de nombreux articles que déterminer la constante de Cheeger d'un graphe est -hard. Cela semble être un théorème populaire, mais je n'ai jamais trouvé ni citation ni preuve pour cette affirmation. À qui dois-je donner du crédit? Dans un vieux document (Isoperimetric Numbers of Graphs,...
Quelqu'un peut-il suggérer une bonne et récente enquête sur le comptage des problèmes et / ou des problèmes qui sont #P.
Actuellement, Bitcoin dispose d'un système de preuve de travail (PoW) utilisant SHA256. D'autres fonctions de hachage utilisent des graphiques d'utilisation du système de preuve de travail, l'inversion partielle de la fonction de hachage. Est-il possible d'utiliser un problème de décision dans la...
Je m'intéresse au problème d'emballer des copies identiques de rectangles (2 dimensions) dans un polygone convexe (2 dimensions) sans chevauchements. Dans mon problème, vous n'êtes pas autorisé à faire pivoter les rectangles et pouvez supposer qu'ils sont orientés parallèlement aux axes. On vous...
Pour une constante , on peut déterminer en temps linéaire, étant donné un graphe d'entrée G , si sa largeur d'arbre est ≤ k . Cependant, lorsque k et G sont donnés en entrée, le problème est NP-difficile. ( Source ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Cependant, lorsque le graphe d'entrée est...
Le problème Not All Equal -SAT (NAE k -SAT), étant donné un ensemble C de clauses sur un ensemble X de variables booléennes telles que chaque clause contient au plus k littéraux, demande s'il existe une affectation de vérité des variables telles que chaque clause contient au moins un vrai et au...
Pour un alphabet fini fixe , un langage formel sur est régulier s'il existe un automate fini déterministe (DFA) sur qui accepte exactement .L ΣΣΣ\SigmaLLLΣΣ\SigmaLΣΣ\SigmaLLL Je m'intéresse aux langues qui sont "presque" régulières dans le sens où elles peuvent être reconnues par des familles...
J'essaie de comprendre la relation entre l'isomorphisme des graphes et le problème des sous-groupes cachés. Y a-t-il une bonne référence pour
Certains d'entre vous ont peut-être suivi cette question , qui a été fermée en raison d'un niveau de recherche insuffisant. J'extrais donc la partie de la question qui se situe au niveau de la recherche. Au-delà des techniques "plus simples", telles que la réduction au tri ou un problème...
Je viens de réaliser que je supposais que la réponse à ma question était "oui" mais je n'ai pas de bonne raison. J'imagine qu'il y a peut-être un garbage collector qui n'introduit que le ralentissement pire des cas. Y a-t-il une référence définitive que je peux citer? Dans mon cas, je travaille sur...
Quelqu'un connaît-il des références qui définissent précisément le lien entre l' algorithme d'unification et l'élimination gaussienne? Je suis particulièrement intéressé par la relation entre les substitutions triangulaires et les décompositions LU. Wayne Snyder et Jean Gallier mentionnent cette...
Cette question concerne la complexité temporelle de l' algorithme de flux maximal de Ford-Fulkerson lors de l'utilisation de DFS pour trouver des chemins d'augmentation. Il existe un exemple bien connu montrant qu'en utilisant DFS, on peut avoir besoin d'un nombre linéaire d'itérations dans le flux...
Un tenseur est une généralisation de vecteurs et de matrices à des dimensions supérieures et le rang d'un tenseur généralise également le rang d'une matrice. A savoir, le rang d'un tenseur TTT est le nombre minimum de rang un tenseurs cette somme à TTT . Un vecteur et une matrice sont des tenseurs...
En bricolant avec l'analyse LR non canonique, j'ai pensé à une méthode d'analyse (avec des tables de taille infinie, ce qui la rend peu pratique ) capable d'analyser exactement les grammaires sans ambiguïté en temps , et je me suis demandé s'il était possible de faire mieux :O(n2)O(n2)O(n^2) Toutes...
Je me demandais quels papiers je devrais lire pour comprendre cette question Une connexion inattendue à d'autres domaines des mathématiques tels que la géométrie algébrique ou la cohomologie supérieure. Peut-être même un domaine des mathématiques pas encore développé. Peut-être que quelqu'un...