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...
Dans l'état actuel des choses, cette question ne convient pas à notre format de questions / réponses. Nous nous attendons à ce que les réponses soient étayées par des faits, des références ou une expertise, mais cette question suscitera probablement un débat, des arguments, des sondages ou une...
Inspiré par cette question , quels sont les problèmes majeurs et les solutions existantes qui nécessitent une amélioration dans le domaine des systèmes distribués (théoriques). Quelque chose comme les protocoles d'adhésion, la cohérence des
Où puis-je trouver des graphiques relatifs à des problèmes réels? Je connais deux référentiels: Collection Sparse Matrix de l'Université de Floride Bodlaender's TreewidthLib
C'est dans la ligne des " Algorithmes du livre ". Bien que les réductions soient également des algorithmes, je pensais qu'il était douteux que l'on pense à une réduction en réponse à la question sur les algorithmes du livre. D'où une requête distincte! Les réductions de toutes sortes sont les...
Je recherche des langages qui ne sont "probablement pas sans contexte" mais nous ne sommes pas en mesure de le (dé) prouver en utilisant des techniques standard connues. Y a-t-il une enquête récente sur le sujet ou une section de problème ouvert d'une conférence récente? Il n'y a probablement pas...
Il existe de nombreux endroits où les nombres ππ\pi et ( 1 + 5-√) / 2(1+5)/2(1+\sqrt5)/2apparaissent. Je suis curieux de connaître les algorithmes dont le temps d'exécution contient le nombre d'or ouππ\pidans
J'utilisais Jung ( http://jung.sourceforge.net/ ) pour visualiser le classement des pages et je l'ai trouvé un peu lent et difficile à mettre à l'échelle au-delà de 100 nœuds. Je me demandais quels autres outils les gens utilisent pour l'analyse et la visualisation des réseaux / réseaux...
Dans cette question , nous semblons avoir identifié un problème naturel qui est NP-complet sous des réductions aléatoires, mais peut-être pas sous des réductions déterministes (bien que cela dépende des hypothèses non prouvées dans la théorie des nombres qui sont vraies). Existe-t-il d'autres...
Verrouillé . Cette question et ses réponses sont verrouillées car la question est hors sujet mais a une signification historique. Il n'accepte pas actuellement de nouvelles réponses ou interactions. Quels algorithmes sont utilisés le plus souvent? Veuillez écrire un seul algorithme par réponse,...
Je pense que ce serait une bonne idée de faire une liste de théorèmes indiquant que P n'est pas égal à NP si et seulement si telle ou telle sortie, une classe de complexité est contenue dans une autre classe de complexité et ainsi de suite et ainsi de suite.
Quelles universités ont un solide programme d'informatique quantique et proposent un certain type de cours d'informatique quantique / d'information / de recherche? Le but ici est de rassembler une liste utile pour ceux qui envisagent des études supérieures dans ces domaines, et non de discuter de...
J'aimerais savoir s'il y a eu des conjectures qui n'ont pas été prouvées depuis longtemps dans le TCS, qui ont ensuite été prouvées par une implication d'un autre théorème, qui auraient pu être plus faciles à prouver.
Je n'ai jamais vu d'algorithme avec un journal dans le dénominateur auparavant, et je me demande s'il existe des algorithmes réellement utiles avec ce formulaire? Je comprends beaucoup de choses qui pourraient entraîner la multiplication d'un facteur de journalisation pendant l'exécution, par...
Je suis un étudiant diplômé en mathématiques avec une solide expérience en logique. J'ai suivi un cours d'un an sur la logique avec des cours de troisième cycle sur la théorie des modèles finis et un autre sur le forçage et la théorie des ensembles. La plupart des textes CS semblent n'assumer qu'un...
Existe-t-il des conjectures en informatique théorique qui impliquent certains paramètres n et qui ont été prouvées pour de petites valeurs de n ET pour des nombres premiers mais qui se sont révélées fausses par la suite? Dans la théorie des nombres, de tels problèmes existent, par exemple. comme le...
Quels sont les principaux problèmes de complexité de calcul ouverts qui découlent des langages de programmation, en particulier l'analyse et la compilation de programmes? Je recherche des problèmes du type "la complexité temporelle de l'inférence de type Hindley-Milner" ou "la complexité temporelle...
Larry Wasserman a récemment publié un article dans lequel il parle de la "police p-value". Il fait un point intéressant (tout l'accent est mis sur moi) (la prémisse en italique que j'ai ajoutée et sa réponse ci-dessous): La plainte la plus courante est que les physiciens et les journalistes...
Quels sont quelques exemples majeurs de dérandomisation réussie ou du moins de progrès dans la démonstration de preuves concrètes vers l' objectif (pas la connexion de dureté aléatoire)?P= BPPP=BPPP=BPP Le seul exemple qui me vient à l'esprit est le test de primalité polynomiale déterministe AKS...
Il existe un certain nombre d'algorithmes et de structures de données qui exploitent l'idée que obtient sa valeur minimale à k = \ sqrt n . Les exemples courants incluent k = √max { k , n / k }max{k,n/k}\max \left\{k, n/k\right\}k = n--√k=nk=\sqrt n algorithme pas à pas géant pour calculer le...