Au cours de ma carrière universitaire, j'ai lu plusieurs articles sur divers sujets liés à l'informatique. Beaucoup impliquent une implémentation et une évaluation de cette implémentation, mais j’ai trouvé que très peu d’entre eux publient le code qu’ils ont utilisé. Pour moi, les avantages...
L'affacturage n'est pas connu pour être NP-complet. Cette question portait sur les conséquences de la factorisation de NP-complet. Curieusement, personne n’a demandé les conséquences de l’affacturage dans P (peut-être parce qu’une telle question est triviale). Donc mes questions sont: Quelles...
Alan Turing , l'un des pionniers de l'informatique (théorique), a apporté de nombreuses contributions scientifiques fondamentales à notre domaine, notamment la définition des machines de Turing, la thèse de Church-Turing, l'indécidabilité et le test de Turing. Cependant, ses importantes découvertes...
Nous entendons souvent parler de recherches classiques et de publications dans le domaine de la complexité informatique (Turing, Cook, Karp, Hartmanis, Razborov, etc.). Je me demandais s'il y avait des articles récemment publiés considérés comme essentiels et à lire absolument. Récemment, je veux...
Le problème, bien sûr, est le double comptage. Il est assez facile à faire pour certaines classes de DAG = un arbre, voire un arbre parallèle-série. Le seul algorithme que j'ai trouvé qui fonctionne sur les DAG généraux en un temps raisonnable est approximatif (Synopsis diffusion), mais augmenter...
Le problème de bande passante minimum est de trouver un ordre des nœuds de graphe sur une ligne entière qui minimise la distance la plus grande entre deux nœuds adjacents quelconques. Une chenille est un arbre formé à partir de la trajectoire principale par la croissance de trajectoires dont les...
Beaucoup pensent que . Cependant, nous savons seulement que est dans le deuxième niveau de la hiérarchie polynomiale, c'est-à-dire . Un pas vers montrant B P P = P est d'abord de faire descendre au premier niveau de la hiérarchie polynomiale, soit B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} =...
Si on restreint Turing Machines à une bande finie (c'est-à-dire d'utiliser un espace délimité ), le problème d'arrêt est décidable, essentiellement parce qu'après plusieurs étapes (pouvant être calculées à partir du nombre d'états Q , S et taille de l'alphabet), une configuration doit être...
J'ai suivi un cours une fois sur la calculabilité et la logique. Le matériel comprenait une corrélation entre les classes de complexité / calculabilité (R, RE, co-RE, P, NP, Logspace, ...) et la logique (Calcul de prédicats, logique du premier ordre, ...). La corrélation comprenait plusieurs...
Nous savons que si vous avez une machine PSPACE, elle est suffisamment puissante pour donner une preuve interactive de la hiérarchie polynomiale à n’importe quel niveau. (Et si je me souviens bien, tout ce que vous avez besoin est #P.) Mais si vous voulez donner une preuve interactive de l'...
Il y a quelques années, Joel Friedman avait écrit un article reliant les limites inférieures du circuit à la cohomologie de Grothendieck (voir articles: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Cette ligne de pensée a-t-elle apporté de nouvelles informations sur la...
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...
Nous "savons" que porte le nom de Steve Cook et que porte le nom de Nick Pippenger. Si je ne me trompe pas, Steve Cook a été nommé NC en l'honneur de Nick Pippenger, et on m'a dit que l'inverse est également vrai. Cependant, je n'ai pu trouver aucune preuve de ce dernier fait ni dans l'article de...
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...
Du point de vue du sens commun, il est facile de croire que l’ajout du non-déterminisme à PP\mathsf{P} étend considérablement son pouvoir, c’est-à-dire que NPNP\mathsf{NP} est beaucoup plus grand que PP\mathsf{P} . Après tout, le non-déterminisme permet un parallélisme exponentiel, qui apparaît...
Je ne pense pas comprendre les classes de types. J'ai lu quelque part que penser que les classes de type sont des "interfaces" (de OO) implémentées par un type est faux et trompeur. Le problème, c'est que j'ai du mal à les voir comme quelque chose de différent et que c'est faux. Par exemple, si...
En 1995, Russell Impagliazzo a proposé cinq mondes de complexité: 1- Algorithmique: P= NPP=NPP=NP avec toutes les conséquences étonnantes. 2- Heuristica: problèmes complets sont difficiles dans le pire des cas ( P ≠ N PNPNPNPP≠ NPP≠NPP \ne NP ) mais sont efficacement résolubles dans le cas moyen....
J'ai une question historique. J'essaie de déterminer la référence pour le fait que la possibilité de coloration sur 3 des graphes (ou colourability pour un ) est NP-difficile.k ≥ 3kkkk ≥ 3k≥3k\geq 3 La réponse tentante est «le papier original de Karp», mais c'est faux. Voici une analyse:...
Cette question a été posée à Jeannette Wing après sa présentation de PCAST sur la science informatique. «Du point de vue de la physique, y a-t-il un volume maximal d'informations que nous pouvons avoir?» (Une question intéressante pour la communauté informatique théorique, car je pense que cela...