Le titre en dit plus ou moins, mais je suppose que je pourrais ajouter un peu de contexte et quelques exemples spécifiques qui m'intéressent. Les théoriciens de la complexité descriptive, tels que Immerman et Fagin, ont caractérisé la plupart des classes de complexité les plus connues à l'aide de...
Y a-t-il eu des recherches sur la mise en œuvre de constructions d'extracteurs aléatoires? Il semble que les preuves d'extraction utilisent Big-Oh, laissant la possibilité de grandes constantes cachées, rendant les implémentations programmatiques potentiellement irréalistes. Un peu de contexte: je...
Est - il possible de construire un explicite 0 / 1 matrix avec N 1,5 ceux de telle sorte que tous les N 0,499 × N 0,499 sous - matrice contient moins de N 0,501 celles?N× NN×NN \times N 0 / 10/10/1N1,5N1.5N^{1.5}N0,499× N0,499N0.499×N0.499N^{0.499} \times N^{0.499}N0,501N0.501N^{0.501} Ou il est...
Discussion : J'ai passé un peu de temps récemment à apprendre différentes choses sur la complexité de la communication. Par exemple, je me suis familiarisé avec le chapitre pertinent d'Arora / Barak, j'ai commencé à lire certains articles et commandé le livre de Kushilevitz / Nisan. Intuitivement,...
Un objectif important des méthodes formelles est de prouver l'exactitude des systèmes, par des moyens automatisés ou dirigés par l'homme. Cependant, il semble que même si vous pouvez fournir une preuve d'exactitude, vous ne pourrez PAS garantir que le système n'échouera pas. Par exemple: La...
Définissez la classe suivante de langues "circulaires" sur un alphabet fini Sigma. En fait, le nom existe déjà pour désigner une chose différente, semble-t-il, utilisée dans le domaine de l'informatique ADN. AFAICT, c'est une classe de langues différente. Un langage L est circulaire ssi pour tous...
Un collègue qui travaille sur la programmation génétique m'a posé la question suivante. J'ai d'abord essayé de le résoudre sur la base d'une approche gourmande, mais sur une deuxième pensée, j'ai trouvé un contre-exemple à l'algorithme gourmand. J'ai donc pensé qu'il valait la peine de le...
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...
Cette question est similaire à une question plus générale pour savoir quel est le bon modèle théorique d'un ordinateur pour concevoir des algorithmes et des structures de données. Ici, je pose des questions spécifiquement sur les ordinateurs haute performance actuels (comme ceux répertoriés dans le...
Le théorème de Karp – Lipton déclare que si , alors s'effondre en . Par conséquent, en supposant des séparations entre et , aucun problème complet n'appartiendra à .P H Σ P 2 Σ P 2 Σ P 3 N P P / p o l yN P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P
Cette question est principalement liée à un problème pratique d'ingénierie logicielle, mais je serais curieux de savoir si les théoriciens pourraient fournir plus d'informations. En termes simples, j'ai une simulation de Monte Carlo qui utilise un générateur de nombres pseudo-aléatoires, et je...
Cinq questions liées sont posées, et une seule réponse intégrée est espérée: Q1: Existe-t-il des langues LLL reconnues uniquement par ces machines Turing PPP dontles exposants d'exécution sont indécidables? Q2: Des exemples de ces machines de Turing peuvent-ils être finement construits? Q3: Ces...
En complexité paramétrée, ⊆ W [ 2 ] ⊆ … ⊆ W [ P ] . On suppose que chacune des enceintes est appropriée.F P T ⊆ W [1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Si alors P = W [ P ]...
Supposons qu'un graphe à n sommets soit présenté comme un flux de m arêtes, mais plusieurs passes sont autorisées sur le flux.gGGnnnmmm Monika Rauch Henzinger, Prabhakar Raghavan et Sridar Rajagopalan ont observé que l' espace est nécessaire pour déterminer s'il existe un chemin entre deux sommets...
Quels sont les résultats connus pour trouver un sous-tableau exact à n dimensions dans un tableau à n dimensions? Dans 1D, c'est juste un problème de correspondance de chaînes, KMP le fait en temps linéaire. En 2D, cet article a montré que cela peut être fait en temps linéaire avec peu d'espace...
Par exemple, dans les langages de programmation, il est courant d'écrire un compilateur / interprète X-in-X, mais à un niveau plus général, de nombreux systèmes Turing-complets connus peuvent se simuler de manière impressionnante (par exemple, simuler le jeu de la vie de Conway dans le jeu de la...
Le théorème PCP indique qu'il n'y a pas d'algorithme de temps polynomial pour MAX 3SAT pour trouver une affectation satisfaisant 7/8 clauses d'une formule 3SAT satisfaisante à moins que .P = N P7 / huit + εsept/8+ϵ7/8+ \epsilonP= NPP=NPP = NP Il existe un algorithme de temps polynomial trivial qui...
Il s'agit d'une reformulation d'une question antérieure . Considérez le jeu d' information parfait et impartial suivant entre deux joueurs, Alice et Bob. Les joueurs reçoivent une permutation des nombres entiers 1 à n. A chaque tour, si la permutation actuelle augmente, le joueur actuel perd et...
J'ai récemment lu ce résumé des problèmes liés à la différence entre les arbres et cela m'a intéressé à savoir quel est l'état de l'art pour ce problème. Supposons également qu'entre vos opérations d'édition autorisées se trouvent le nœud d'ajout / suppression traditionnel, le contenu d'édition,...
Avertissement: je ne suis pas un théoricien CS. Issu de l'algèbre abstraite, j'ai l'habitude de traiter des choses qui sont égales à un isomorphisme - mais j'ai du mal à traduire ce concept en structures de données. J'ai d'abord pensé que des morphismes bijectifs théoriques définis suffisaient,...