J'ai deux questions historiques: Qui a décrit en premier le calcul non déterministe? Je sais que Cook a décrit des problèmes NP-complets et qu'Edmonds a proposé que les algorithmes P soient des algorithmes "efficaces" ou "bons". J'ai cherché dans cet article Wikipedia et j'ai survolé "Sur la...
Il existe une grande littérature sur les «tests de propriétés» - le problème de faire un petit nombre de requêtes de boîte noire à une fonction pour distinguer deux cas:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff is a member of some class of functions CC\mathcal{C} fff is εε\varepsilon-far from...
Je recherche du matériel didactique qui couvre les preuves d'exactitude du compilateur, de préférence en utilisant des méthodes de dénotation, au niveau d'un étudiant débutant. Alternativement, connaissez-vous quelques exemples de compilateur simples que je pourrais utiliser pour illustrer les...
Une chaîne d'addition est une séquence d'entiers positifs où et chaque index , nous avons pour certains indices . La longueur de la chaîne d'addition est ; la cible de la chaîne d'addition est .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i n x n(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dots,...
Un problème classique dans la théorie des probabilités est d'exprimer la probabilité d'un événement en termes d'événements plus spécifiques. Dans le cas le plus simple, on peut dire . Write Let pour l'événement .A B A ∩ BP[ A ∪ B ] = P[ A ] + P[ B ] - P[ A ∩ B ]P[UNE∪B]=P[UNE]+P[B]-P[UNE∩B]P[A \cup...
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...
Alors que le théorème d'Adleman montre que , je ne connais aucune littérature qui étudie l'inclusion possible de . Quelles seraient les conséquences théoriques de la complexité d'une telle inclusion?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP}...
Je recherche une bonne enquête sur les algorithmes et la complexité de l'algèbre linéaire (opérations comme le rang, l'inverse, les valeurs propres, ... pour les matrices booléennes, et entières / rationnelles) en mettant l'accent sur les algorithmes parallèles ( hiérarchie N C ) et polytemporels ....
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...
Dans la classe de complexité , il y a des problèmes supposés NE PAS être dans la classe , c'est-à-dire des problèmes avec des algorithmes parallèles déterministes. Le problème du débit maximal en est un exemple. Et il y a des problèmes que l'on croyait être dans , mais aucune preuve n'a encore été...
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...
Le problème intéressant suivant est apparu récemment dans mes recherches: INSTANCE: Graphique .G ( V, E)G(V,E)G(V, E) SOLUTION: un achèvement de cycle impair sans corde, défini comme un surensemble de l'ensemble de bords E de sorte que le graphe complété G ' ( V , E ' ) a la propriété que chaque...
Wikipedia fournit des exemples de problèmes où la version de comptage est difficile, alors que la version de décision est facile. Certains d'entre eux comptent des appariements parfaits, comptant le nombre de solutions à 222 -SAT et le nombre de tri topologiques. Existe-t-il d'autres classes...
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...
(Cette question est un peu une "enquête".) Je travaille actuellement sur un problème où j'essaie de partitionner les bords d'un tournoi en deux ensembles, qui sont tous deux nécessaires pour remplir certaines propriétés structurelles. Le problème "semble" assez difficile, et je m'attends à ce que...
Existe-t-il un aperçu des algorithmes de calcul des interpolants? Qu'en est-il des articles sur un seul algorithme? Le cas qui m'intéresse le plus est et C = q , plus la contrainte que l'interpolant est aussi petit que possible. (Je connais l'article de McMillan de 2005 , qui décrit comment obtenir...
Quelle est la complexité temporelle (et non la complexité des requêtes) de l'algorithme de Grover? Il me semble clair qu'il s'agit de car il existe des itérations et chaque itération nécessite l'utilisation de l'opération de réflexion qui à son tour prend du temps utilisant n'importe quel ensemble...
Prédire la bourse est difficile! TCS peut-il rendre ce sentiment plus formel? Récemment, j'ai commencé à réfléchir un peu à la finance et je me demandais en quoi la connaissance du TCS pouvait aider. Les fonds spéculatifs et les sociétés d'investissement semblent utiliser le trading algorithmique,...
En calcul quantique adiabatique (AQC), on code la solution d'un problème d'optimisation à l'état fondamental d'un [problème] hamiltonien . Pour arriver à cet état fondamental, vous commencez dans un état initial (fondamental) facilement refroidissable avec Hamiltonian H i et "recuit" (perturber...
Question principale / générale Soit LLL une langue. Définissez les langues LiLiL_i avec L0=LL0=LL_0 = L et Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} pour . Considérez . Donc, nous "incorporons" à plusieurs reprises en lui-même pour obtenir .i≥1i≥1i \geq...