Après avoir entendu Emo Welzl parler du sujet cet été, je sais que le nombre de triangulations d'un ensemble de points dans le plan se situe entre environ et . Toutes mes excuses si je ne suis pas à jour; les mises à jour sont les bienvenues.nnnΩ(8.48n)Ω(8.48n)\Omega(8.48^n)O(30n)O(30n)O(30^n) J'ai...
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
Je sais que (nombre d'appels logarithmiques à l'oracle NP) est équivalent à (polynôme nombre de requêtes parallèles à l’oracle NP). Je me demandais si la version "fonctionnelle" de ces classes était également équivalente, c'est-à-dire siP N P | |PN P [logn
Cette question est liée à l'une de mes questions précédentes, les problèmes NP-difficiles sur les arbres . Je recherche des problèmes P-complets sur les arbres.
Y aurait-il des conséquences majeures si SAT avait tout au plus des preuves non-exponentielles sous-exponentielles ou encore plus fortement, SAT avait des algorithmes de temps
J'ai de la difficulté à comprendre une étape dans le document de Dobkin et Kirkpatrick sur la séparation des polyèdres. J'essaie de comprendre cette version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Il soutient qu'après avoir connu la meilleure séparation de...
Cette question est inspirée d'un commentaire de Jukka Suomela sur une autre question . Quels sont les exemples de problèmes de calcul infiniment grands mais localement finis (et algorithmes)? En d'autres termes, quels sont les exemples de calculs qui s'arrêtent dans un temps fini, dans lesquels...
Considérez le problème de trouver le nombre maximum de chevaliers qui peuvent être placés sur un échiquier sans que deux d'entre eux ne s'attaquent. La réponse est 32: il n'est pas trop difficile de trouver une correspondance parfaite (le graphique induit par les mouvements de chevalier est...
L'énoncé de recherche de JM Siskind déclare: Staline est un compilateur d'optimisation pour Scheme qui effectue une analyse statique du programme entier et utilise les résultats de cette analyse pour générer du code extrêmement efficace. Staline utilise une large collection de techniques d'analyse...
J'implémente un système dont une partie nécessite de l'aide. Je le conçois donc comme un problème de graphe pour le rendre indépendant du domaine. Problème: On nous donne un graphe acyclique dirigé . Sans perte de généralité, supposons que G a exactement un sommet source s et exactement un sommet...
Le problème de bande passante du graphique est défini comme suit. Étant donné un graphe , une disposition de est un mappage un à un des sommets de sur les entiers . La largeur de bande de est définie commeG=(V,E)G=(V,E)G=(V,E) G G { 1 , … , | V | } ffffGGGGGG{1,…,|V|}{1,…,|V|}\{1, \ldots, |V|\}fff...
Question. Dans leur article Improved simulation of stabilizer circuits , Aaronson et Gottesman affirment que la simulation d'un circuit CNOT est ⊕L - complete (sous les réductions de l'espace de log). Il est clair qu'il est contenu dans ⊕L ; comment le résultat de dureté tient-il? De manière...
Dans l'article de Ben-Dor / Halevi [1], il est donné une autre preuve que le permanent est #P#P\#P complet. Dans la dernière partie de l'article, ils montrent la chaîne de réduction IntPerm∝NoNegPerm∝2PowersPerm∝0/1-PermIntPerm∝NoNegPerm∝2PowersPerm∝0/1-Perm\begin{equation} \text{IntPerm} \propto...
Je m'intéresse à la première histoire des résultats publiés sur les compromis spatio-temporels à usage général. En particulier, je veux savoir qui a décrit en premier le type d'algorithme suivant pour évaluer un calcul ayant un graphique de flux de données arbitraire avec en degré O (1) en...
Je me demande comment trouver la circonférence d'un graphe non orienté clairsemé. Par clairsemé, je veux dire . Par optimal, j'entends la complexité temporelle la plus faible.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) J'ai pensé à une modification de l'algorithme de Tarjan pour les graphiques non orientés,...
(déjà demandé sur le site principal , mais aussi ici pour une meilleure couverture, désolé) Depuis que je connaissais les structures de données succinctes, j'ai désespérément besoin d'une bonne vue d'ensemble des développements les plus récents dans ce domaine. J'ai googlé et lu beaucoup d'articles...
Pour autant que je sache, presque toutes les implémentations de QKD utilisent l'algorithme CASCADE de Brassard et Salvail pour la correction des erreurs. Est-ce vraiment la méthode la plus connue pour corriger les erreurs dans une séquence partagée de qubits aléatoires, ou existe-t-il une meilleure...
Quelle est la complexité de calcul de l'optimisation de diverses fonctions sur le groupe unitaire ?U(n)U(n)\mathcal{U}(n) Une tâche typique, résultant souvent en théorie quantique de l' information, on maximiser le nombre de types (ou des polynômes d'ordre supérieur en U ) sur l' ensemble des...
Il serait intéressant de rassembler une liste de conditions qui impliquent qu'un langage sans contexte L est régulier, c'est-à-dire des conditions de la forme: "si un CFG / PDA donné a la propriété P, alors ses langages sont réguliers" La propriété P n'a pas à caractériser les CFG générant des...
Je m'intéresse au problème "le plus proche" (et "le plus complexe") de la conjecture de Collatz qui a été résolue avec succès (ce que Erdos a dit fameusement "les mathématiques ne sont pas encore mûres pour de tels problèmes"). Il a été prouvé qu'une classe de problèmes "de type Collatz" est...