Problème algorithmiqueUn problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier.
Circuit complexityIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.
Langage rationnelEn théorie des langages, les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes : ce sont les langages décrits par les expressions régulières ou rationnelles, d'où le nom de langages réguliers ; ce sont les langages obtenus, à partir des lettres et de l'ensemble vide, par les opérations rationnelles, à savoir l'union, le produit et l'étoile de Kleene, d'où le nom de langages rationnels ; ce sont les langages reconnus par des auto
Complet (complexité)En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème. Un problème p est dit difficile pour une classe C pour un certain type de réduction s'il existe une réduction de ce type, depuis n'importe quel problème de la classe vers p.
Machine de Turing alternanteEn informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981.
Réduction en espace logarithmiqueEn théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique. La machine de Turing utilisée pour une réduction en espace logarithmique est constituée de trois rubans au lieu d'un : un ruban d'entrée (en lecture seule), un ruban de travail (de taille logarithmique en la taille du ruban d'entrée), et un ruban de sortie (en écriture seule et tel que la tête d'écriture ne peut écrire deux fois sur une même case).
Complémentaire (complexité)En théorie de la complexité (un domaine de l'informatique théorique), on parle du complémentaire d'une classe C, noté co-C ou coC, pour désigner l'ensemble des langages complémentaires des langages de la classe. Cet opérateur amène à considérer de nouvelles classes comme co-NP, le complémentaire de NP. Soit un langage sur l'alphabet , et , l'ensemble des mots sur . Alors le complémentaire de , noté ici est . On remarque en particulier que le complémentaire de est . Soit C une classe, alors son complémentaire co-C est : .
Quantum complexity theoryQuantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA.
Thèse de Cobhamthumb|Le graphique montre le temps en millisecondes pour résoudre des instances du problème du sac à dos en fonction de la taille d'entrée n. L'expérience a été réalisée sur un ordinateur Pentium III 933 MHz (les données proviennent d'une moyenne sur 100 instances à chaque fois). En informatique, la thèse de Cobham, aussi connue sous la thèse de Cobham–Edmonds (nommée d'après Alan Cobham et Jack Edmonds) postule que les problèmes calculables « facilement » sont les problèmes calculables en temps polynomial.
Algorithme de Las VegasEn informatique, un algorithme de Las Vegas est un type d'algorithme probabiliste qui donne toujours un résultat correct ; son caractère aléatoire lui donne de meilleures performances temporelles en moyenne. Comme le suggère David Harel dans son livre d'algorithmique, ainsi que Motvani et Raghavan, le tri rapide randomisé est un exemple paradigmatique d'algorithme de Las Vegas.
