J'ai une base très forte en algèbre, à savoir algèbre commutative, algèbre homologique, théorie des champs, théorie des catégories, et j'apprends actuellement la géométrie algébrique. Je suis un étudiant en mathématiques avec une tendance à passer à l'informatique théorique. En gardant à l'esprit...
J'entends souvent dire que pour de nombreux problèmes, nous connaissons des algorithmes randomisés très élégants, mais pas, ou seulement des solutions déterministes plus compliquées. Cependant, je n'en connais que quelques exemples. Plus en évidence Tri rapide randomisé (et algorithmes géométriques...
En tant qu'amateur de TCS, je lis du matériel très introductif sur l'informatique quantique. Voici les quelques informations élémentaires que j'ai apprises jusqu'à présent: Les ordinateurs quantiques ne sont pas connus pour résoudre des problèmes NP-complets en temps polynomial. "La magie quantique...
Dans l'esprit de certaines discussions générales comme celle- ci, j'ouvre ce fil avec l'intention de recueillir des opinions sur les défis ouverts et les sujets brûlants de la recherche sur les langages de programmation . J'espère que la discussion pourra même faire émerger des opinions sur...
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...
Deux des hypothèses courantes pour prouver la dureté des résultats d'approximation sont et Conjecture de jeux uniques. Existe-t-il une dureté des résultats d'approximation en supposant que N P ≠ c o N P ? Je recherche le problème A tel qu'il "est difficile d'approximer A à l' intérieur d'un facteur...
Il est impossible d'écrire un langage de programmation qui autorise toutes les machines qui s'arrêtent sur toutes les entrées et aucune autre. Cependant, il semble facile de définir un tel langage de programmation pour n'importe quelle classe de complexité standard. En particulier, nous pouvons...
Il y a une justification philosophique souvent citée pour croire que P! = NP même sans preuve. D'autres classes de complexité ont la preuve qu'elles sont distinctes, car sinon, il y aurait des conséquences "surprenantes" (comme l'effondrement de la hiérarchie polynomiale). Ma question est, quelle...
Avertissement: je ne peux que me porter garant de mes domaines de recherche, à savoir les méthodes formelles, la sémantique et la théorie du langage de programmation. La situation est peut-être différente dans d'autres parties de la discipline. Il semble que le TCS soit devenu plutôt axé sur les...
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
J'ai une certaine expérience dans le calcul scientifique et j'ai largement utilisé les arbres kd pour les applications BSP (partitionnement d'espace binaire). Je me suis récemment familiarisé avec les octrois, une structure de données similaire pour partitionner des espaces euclidiens 3D, mais qui...
J'ai parfois entendu des gens parler d'algorithmes quantiques et d'états et de la possibilité d'envisager plusieurs possibilités à la fois, mais je n'ai jamais réussi à demander à quelqu'un d'expliquer le modèle de calcul derrière cela. Pour être clair, je ne demande pas comment les ordinateurs...
Dans l'article The Random Oracle Hypothesis Is False , les auteurs (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan et Rohatgi) discutent des implications de l' hypothèse de l'oracle aléatoire . Ils soutiennent que nous savons très peu de choses sur les séparations entre les classes de...
Existe-t-il une structure de données de file d'attente prioritaire qui prend en charge les opérations suivantes? Insérer (x, p) : ajouter un nouvel enregistrement x avec la priorité p StableExtractMin () : Renvoie et supprime l'enregistrement avec une priorité minimale, rompant les liens par ordre...
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...
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...
Dans cette question, une formule 3CNF signifie une formule CNF où chaque clause implique exactement trois variables distinctes . Pour un 0 < s <1 constant , Gap-3SAT s est le problème de promesse suivant: Gap-3SAT de l' instance : A 3CNF formule de φ. Oui-promesse : φ est satisfaisable. Pas...
Cette question concerne les problèmes pour lesquels il existe un grand écart de complexité ouvert entre la borne inférieure connue et la borne supérieure, mais pas en raison de problèmes ouverts sur les classes de complexité elles-mêmes. Pour être plus précis, disons qu'un problème a des classes...
Je suis nouveau dans le domaine CS et j'ai remarqué que dans la plupart des articles que j'ai lus, il n'y a pas de résultats empiriques (pas de code, juste des lemmes et des preuves). Pourquoi donc? Étant donné que l'informatique est une science, ne devrait-elle pas suivre la méthode...
Y a-t-il une borne inverse de Chernoff qui limite la probabilité de queue au moins autant. c'est-à-dire si X1,X2,…,XnX1,X2,…,XnX_1,X_2,\ldots,X_n sont des variables aléatoires binomiales indépendantes et μ=E[∑ni=1Xi]μ=E[∑i=1nXi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Alors peut-on prouver...