Il semble que la théorie de la complexité géométrique nécessite une connaissance approfondie des mathématiques pures telles que la géométrie algébrique, la théorie de la représentation. Bien que je sois un étudiant en informatique et que je n’ai PAS de cours de mathématiques très abstraites et...
Existe-t-il des références (en ligne ou sous forme de livre) qui organisent et discutent des théorèmes du SDC par technique de démonstration? Garey et Johnson le font pour les différents types de constructions de widgets nécessaires pour les preuves de complétude NP (en particulier dans le chapitre...
La complexité croissante des programmes informatiques et la position de plus en plus cruciale des ordinateurs dans notre société me laissent nous demander pourquoi nous n'utilisons toujours pas collectivement des langages de programmation dans lesquels vous devez prouver formellement que votre code...
Je vais poser une question assez vague, car la frontière entre l'informatique théorique et les mathématiques n'est pas toujours facile à distinguer. QUESTION: Connaissez -vous des résultats intéressants dans CS qui sont indépendants de ZFC (c'est-à-dire de la théorie des ensembles standard) ou qui...
Un certain nombre de problèmes géométriques sont faciles à prendre en compte dans , mais sont NP-complets dans R d pour d ≥ 2 (y compris l'un de mes problèmes préférés, le cache du disque de l'unité).R1R1R^1RdRdR^dd≥2d≥2d\geq2 Est-ce que quelqu'un connaît un problème qui peut être résolu à tout...
En général, nous savons qu'il est plus facile de tester si une fonction prend une valeur particulière à une entrée donnée que d'évaluer la fonction à cette entrée. Par exemple: L'évaluation du permanent d'une matrice de nombre entier non négatif est # P-difficile, mais indiquer si un tel permanent...
C'est une question non technique, mais certainement pertinente pour la communauté du SDC. Si jugé inapproprié, n'hésitez pas à fermer. La page Web Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) a certainement rendu de grands services à la communauté TCS au fil des ans....
Le problème est de calculer le polynôme . Supposons que tous les coefficients tiennent dans un mot machine, c’est-à-dire qu’ils puissent être manipulés dans le temps unitaire.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Vous pouvez faire fois en appliquant...
Considérez le problème de comptage suivant (ou le problème de décision associé): Étant donné deux entiers positifs codés en binaire, calculez leur plus grand commun diviseur (gcd). Quelle est la plus petite classe de complexité dans laquelle ce problème est contenu? Pouvez-vous fournir une...
Alors que j'ai réussi quelques cours sur la théorie des probabilités, tant au lycée qu'à l'université, j'ai du mal à lire les articles TCS en matière de probabilité. Il semble que les auteurs des articles du TCS connaissent très bien la probabilité. Ils fonctionnent comme par magie avec des...
Définissez LOGLOG comme la classe de langues qui peut être calculée dans l'espace O (loglog n) par une machine de Turing déterministe (avec un accès bidirectionnel à l'entrée). De même, définissez NLOGLOG comme la classe de langues qui peut être calculée dans l'espace O (log log n) par une machine...
J'ai besoin d'un livre de théorie des automates finis avec beaucoup d'exemples que je peux utiliser pour l'auto-apprentissage et pour préparer les
L'examen des questions à travers la lentille algorithmique (c'est-à-dire d'un point de vue algorithmique ou complexe) est devenu utile dans des disciplines en dehors du «domaine standard» de l'informatique. En particulier, CS a eu un impact sur la biologie grâce à la biologie computationnelle, sur...
J'ai lu Nielson & Nielson " Semantics with Applications ", et j'aime vraiment le sujet. J'aimerais avoir un livre de plus sur la sémantique du langage de programmation - mais je ne peux vraiment en obtenir qu'un. J'ai jeté un œil au livre Turbak / Gifford , mais il est trop long; Je pensais que...
Il ne semble pas que cela soit connu - mais y a-t-il des limites inférieures intéressantes sur la complexité de la multiplication matricielle dans le modèle informatique quantique? Avons-nous l'intuition que nous pouvons battre la complexité de l'algorithme Coppersmith-Winograd en utilisant des...
Les méthodes polynomiales , par exemple Nullstellensatz combinatoire et le théorème de Chevalley-Warning sont des outils puissants en combinatoire additive. En représentant un problème avec des polynômes appropriés, ils peuvent garantir l'existence d'une solution ou le nombre de solutions aux...
Dans son livre, Boolean Function Complexity, Stasys Jukna mentionne (page 564) que Kolmogorov croyait que chaque langue en P avait des circuits de taille linéaire. Aucune référence n'est mentionnée et je n'ai rien trouvé en ligne. Quelqu'un en sait-il plus
Je ne connais que deux preuves du lemme de Schwartz – Zippel. La première preuve (plus courante) est décrite dans l' entrée wikipedia . La deuxième preuve a été découverte par Dana Moshkovitz. Existe-t-il d'autres preuves qui utilisent des idées sensiblement différentes?...
Je viens d'enseigner l' algorithme de raccourci aléatoire de Karger-Stein dans ma classe d'algorithmes diplômés. C'est un vrai bijou algorithmique , donc je ne peux pas ne pas l' enseigner, mais cela me laisse toujours frustré, car je ne connais pas d'autres applications de la technique principale....
Edit: J'ai choisi la réponse avec le score le plus élevé avant le 06 décembre 2012. C'est une question douce. Le concept d'algorithmes (déterministes) remonte à la Colombie-Britannique. Qu'en est-il des algorithmes probabilistes? Dans cette entrée wiki , l'algorithme de Rabin pour le problème de...