Informatique théorique

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...

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...

Toute monade est également un foncteur applicatif et tout foncteur applicatif est un foncteur. De plus, tout comonad est un foncteur. Existe-t-il un concept similaire entre les comonades et les foncteurs, quelque chose comme le foncteur co-applicatif, et quelles sont ses propriétés?...

Considérons une permutation σσ\sigma de [1..n][1..n][1..n] . Une inversion est définie comme une paire (i,j)(i,j)(i, j) d'indices tels que i<ji<ji < j et σ(i)>σ(j)σ(i)>σ(j)\sigma(i) > \sigma(j) . Définissez AkAkA_k comme le nombre de permutations de [1..n][1..n][1..n] avec au plus kkk...

La complexité des circuits en profondeur bornée est l'un des principaux domaines de recherche de la théorie de la complexité des circuits. Cette rubrique a des origines dans des résultats comme "la fonction de parité n'est pas dans " et "la fonction mod n'est pas calculée par ", où est la classe...

Dans l'algorithme de Strassen, pour calculer le produit de deux matrices et , les matrices et sont divisées en matrices de blocs et l'algorithme procède calcul récursif de produits matrice-matrice à blocs par opposition à un produit matriciel matriciel à blocs, c'est-à-dire si nous voulons , où B A...

Je recherche des exemples naturels d' algorithmes efficaces (ie en temps polynomial) st leur exactitude et leur efficacité peuvent être prouvées de manière constructive (par exemple en ou ), maisPR APRUNEPRAHUNEHUNEHA aucune preuve utilisant uniquement des concepts efficaces n'est connue...

À partir de Curry-Howard-Lambek, il y a eu une belle trinité de théories de types, de logiques et de catégories. Je suis curieux de savoir quelle sémantique catégorique vous obtenez lorsque vous ajoutez un sous-typage (coercitif) à une théorie des types - il semble que cela n'ait pas été beaucoup...

Récemment, j'ai rencontré la variante suivante de coloration des bords. Étant donné un graphe connexe non orienté, trouvez une coloration des arêtes qui utilise le nombre maximal de couleurs tout en satisfaisant également la contrainte selon laquelle, pour chaque sommet , les arêtes incidentes à...

Une chose que les ordinateurs quantiques peuvent faire (peut-être même avec seulement des circuits quantiques BPP + log-depth) est d'échantillonner approximativement la transformée de Fourier d'une fonction booléenne évaluée en P.±1±1\pm 1 Ici et ci-dessous quand je parle d'échantillonner la...

Considérons le problèmeQQQ suivant Q : On nous donne un entier et k intervalles [ l i , r i ] avec 1 ≤ l i ≤ r i ≤ 2 n . On nous donne également 2 n entiers d 1 , … , d 2 n ≥ 0 . La tâche consiste à sélectionner un nombre minimum d'intervalles [ l i , r i

Lorsqu'on essaie de convaincre les économistes de la pertinence de la théorie de la complexité dans la presse écrite, existe-t-il une référence standard à citer? Je connais le billet de blog de Noam Nisan , l'enquête de Tim Roughgarden et le chapitre 11 de l'essai de Scott Aaronson . Ces articles...

La classe de graphique suivante est-elle connue dans la littérature? La classe de graphes est paramétrée par des entiers positifs et et contient chaque graphe telle sorte que pour chaque sommet , le sous-graphe de induit sur tous les sommets à distance au plus partir de dans a une largeur d'arbre...

Je fais une revue de la littérature sur le problème d'isomorphisme graphique. La plupart des articles que je lis sont écrits par EM Luks et Laszlo Babai. Ces articles utilisent les connaissances de haut niveau de la théorie des groupes et de la théorie de la complexité. Comme je suis nouveau dans...

Je suis actuellement lycéen, intéressé par l'informatique théorique et les mathématiques appliquées. Je me suis autodidacte algèbre linéaire et calcul et mathématiques concrètes. J'ai une idée naïve que pour écrire de meilleurs algorithmes, il faut savoir autant de mathématiques que possible parce...

Une partie des travaux sur la sensibilité par rapport à la sensibilité aux blocs visait à examiner les fonctions avec un écart aussi grand que possible entre s(f)s(f)s(f) et bs(f)bs(f)bs(f) afin de résoudre la conjecture selon laquelle bs(f)bs(f)bs(f) n'est que polynomialement plus grand que...

Supposons que je considère la variante suivante de BPP, qui appelons E (xact) BPP: Une langue est en EBPP s'il y a un TG aléatoire polynomial qui accepte chaque mot de la langue avec exactement 3/4 de probabilité et chaque mot qui n'est pas dans la langue avec exactement 1/4 de probabilité....

En recherchant le système d'information sur les classes de graphes et leurs inclusions , j'ai trouvé plusieurs classes de graphes pour lesquelles le problème du cycle hamiltonien est NP-complet alors que la complexité des problèmes de chemin hamiltonien n'est PAS connue. Certaines de ces classes...

Suite à la suggestion de Josh Grochow, je convertis mon commentaire d'une question précédente en une nouvelle question. Quelles preuves avons-nous pour ?U P ≠ N PUP≠NP\mathsf{UP} \neq \mathsf{NP} Ici est la classe de langages reconnaissable par les machines de Turing non déterministes à temps...

La borne inférieure Blum est la borne inférieure du circuit la plus connue sur la base complète d'une fonction explicite , cf. Réponse de Jukna à cette question pour des résultats connexes.f : { 0 , 1 } n → { 0 , 1 }3 n - o ( n )3n-o(n)3n-o(n)F: { 0 , 1 }n→ { 0 , 1 }F:{0,1}n→{0,1}f : \{0,1\}^n \to...