Avertissement: je connais très peu la théorie de la complexité. Je suis désolé mais il n'y a vraiment aucun moyen de poser cette question sans être (terriblement) concis: Quels devraient être les morphismes dans "la" catégorie des machines de Turing? Ceci est évidemment subjectif et dépend de...
Un de mes étudiants a récemment posé la question suivante: SupposonsDoit-il exister un h (n) tel que DTIME (f (n)) \ subsetneq DTIME (h (n)) \ subsetneq DTIME (g (n))?DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq
Récemment, Babai a publié un article sur le STOC 2016 affirmant que l'isomorphisme des graphes peut être résolu en temps quasi-polynomial. Au début de 2017, Babai a rétracté la réclamation quasi-polynomiale en raison de graves erreurs trouvées par Harald Helfgott. Comme expliqué par Babai lui-même,...
Le théorème de Savitch montre que pour toutes les fonctions suffisamment grandes f , et prouver que cela est serré est un problème ouvert depuis des décennies .N S P A C E (f( n ) ) ⊆ D S P A C E ( f( n )2)NSPUNECE(F(n))⊆réSPUNECE(F(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)FFf...
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...
Il est connu que l'intersection de trois matroïdes généraux est NP-difficile ( source ), ce qui se fait par réduction du cycle hamiltonien. La réduction utilise un matroïde graphique et deux matroïdes de connectivité. Un cas particulier d'un problème sur lequel je travaille peut être résolu par...
Dans "Quantum Computation and Quantum Information" de Mike et Ike, l'algorithme de Grover est expliqué en détail. Cependant, dans le livre, et dans toutes les explications que j'ai trouvées en ligne pour l'algorithme de Grover, il ne semble pas y avoir de mention de la façon dont l'Oracle de Grover...
Nous savons (pour le moment environ 40 ans, merci Adleman, Bennet et Gill) que l'inclusion BPP P / poly, et un BPP / poly P / poly encore plus fort . Le "/ poly" signifie que nous travaillons de manière non uniforme (un circuit séparé pour chaque longueur d'entrée ), tandis que P sans ce "/ poly"...
Étant donné un simple graphe non orienté GGG , trouver un sous-ensemble A≠∅A≠∅A\neq \emptyset de sommets, tel que pour tout sommet x∈Ax∈Ax\in A au moins la moitié des voisins de xxx sont également dans AAA , et la taille de AAA est minimale. Autrement dit, nous recherchons un cluster, dans lequel...
Les algorithmes de hachage de mot de passe couramment utilisés fonctionnent comme ceci aujourd'hui: salez le mot de passe et introduisez-le dans un fichier KDF. Par exemple, en utilisant PBKDF2-HMAC-SHA1, le processus de hachage de mot de passe est DK = PBKDF2(HMAC, Password, Salt, ...). Parce que...
Existe-t-il des exemples intéressants d'algorithmes qui ont été publiés avec des limites prouvées et où des limites strictement meilleures ont été publiées par la suite? Pas de meilleurs algorithmes avec de meilleures limites - c'est évidemment ce qui est arrivé! Mais une meilleure analyse...
Quelle est la variation suivante sur la couverture de l'ensemble appelée? Etant donné un ensemble S, une collection C de sous-ensembles de S et un entier positif K, existe-t-il K ensembles en C tels que chaque paire d'éléments de S se trouve dans l'un des sous-ensembles sélectionnés. Remarque: Il...
Cette question concerne l'algorithme de Fisher-Yates pour renvoyer un mélange aléatoire d'un tableau donné. La page Wikipedia dit que sa complexité est O (n), mais je pense que c'est O (n log n). Dans chaque itération i, un entier aléatoire est choisi entre 1 et i. La simple écriture de l'entier en...
Je recherche un algorithme en ligne pour maintenir la fermeture transitive d'un graphe acyclique dirigé avec une complexité temporelle inférieure à O (N ^ 2) par addition de bord. Mon algorithme actuel est comme ceci: For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes...
Étant donné un langage L défini par une machine de Turing qui le décide, est-il possible de déterminer algorithmiquement si L se situe dans
On dit qu'un problème P est dans APX s'il existe une constante c> 0 telle qu'un algorithme d'approximation polynomiale en temps existe pour P avec le facteur d'approximation 1 + c. APX contient PTAS (vu en choisissant simplement n'importe quelle constante c> 0) et P. APX est-il dans NP? En...
Existe-t-il désormais des algorithmes / preuves plus simples pour trianguler un polygone plan en temps linéaire? Quelle est une bonne ressource sur l'état de l'art de ce fameux
Dans cet article sur "L'emballage de cercle pour la conception d'origami est difficile" par Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, à la page 15, figure 13, ils prétendent que la longueur du côté du plus petit carré qui entoure deux cercles de la zone 1/2 chacun est 1,471299. D'après mes...
Tout en essayant de prouver certaines propriétés de base à l'aide de types coinductifs dans Coq, je continue à rencontrer le problème suivant et je ne peux pas le contourner. J'ai distillé le problème dans un simple script Coq comme suit. Le type d' arbre définit des arbres peut - être infini avec...
Une classe héréditaire de structures (par exemple des graphiques) est une classe qui est fermée sous des sous-structures induites, ou de manière équivalente, est fermée sous suppression de vertex. Les classes de graphiques qui excluent un mineur ont de belles propriétés qui ne dépendent pas du...