Accès plus rapide que le navigateur!
50 relations: BPP (complexité), BQP, Co-NP, Complémentaire (complexité), Complexité en espace, Complexité en temps, DSPACE, DTIME, EXPSPACE, EXPTIME, Extremum, Graphe hamiltonien, Graphe orienté, Informatique théorique, IP (complexité), L (complexité), Leonid Levin, Machine de Turing, Machine de Turing probabiliste, Majorant ou minorant, NC (complexité), NEXPSPACE, NEXPTIME, NL (complexité), NP (complexité), NSPACE, NTIME, P (complexité), P/poly, Parallélisme (informatique), Préordre, Problème algorithmique, Problème de décision, Problème NP-complet, Problème SAT, PSPACE, Réduction polynomiale, Relation (mathématiques), Relation réflexive, Relation transitive, RP (complexité), Stephen Cook, Système de preuve interactive, Thèse de Cobham, Théorème de Cook, Théorème de hiérarchie en temps déterministe, Théorème de Savitch, Théorie de la complexité (informatique théorique), Université de Waterloo, ZPP (complexité).
BPP (complexité)
En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.
Nouveau!!: Classe de complexité et BPP (complexité) · Voir plus »
BQP
En théorie de la complexité des algorithmes BQP (bounded error quantum polynomial time) est la classe des problèmes de décision qui peuvent être résolus par un calculateur quantique en un temps polynomial, avec une probabilité d'erreur d'au plus 1/3 dans tous les cas.
Nouveau!!: Classe de complexité et BQP · Voir plus »
Co-NP
En informatique théorique, co-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision au sens de la théorie de la complexité.
Nouveau!!: Classe de complexité et Co-NP · Voir plus »
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.
Nouveau!!: Classe de complexité et Complémentaire (complexité) · Voir plus »
Complexité en espace
En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées.
Nouveau!!: Classe de complexité et Complexité en espace · Voir plus »
Complexité en temps
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.
Nouveau!!: Classe de complexité et Complexité en temps · Voir plus »
DSPACE
En théorie de la complexité, DSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing déterministe.
Nouveau!!: Classe de complexité et DSPACE · Voir plus »
DTIME
En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe.
Nouveau!!: Classe de complexité et DTIME · Voir plus »
EXPSPACE
En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe.
Nouveau!!: Classe de complexité et EXPSPACE · Voir plus »
EXPTIME
En théorie de la complexité, EXPTIME (ou EXP) est la classe de complexité qui est l'ensemble des problèmes de décision décidés par une machine de Turing déterministe en temps exponentiel.
Nouveau!!: Classe de complexité et EXPTIME · Voir plus »
Extremum
Un extremum (pluriel extrema ou extremums), ou extrémum (pluriel extrémums), est une valeur extrême, soit maximum, soit minimum.
Nouveau!!: Classe de complexité et Extremum · Voir plus »
Graphe hamiltonien
solides de Platon, le dodécaèdre est représenté par un graphe hamiltonien. graphe grille 8x8. En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule.
Nouveau!!: Classe de complexité et Graphe hamiltonien · Voir plus »
Graphe orienté
Un graphe orienté G.
Nouveau!!: Classe de complexité et Graphe orienté · Voir plus »
Informatique théorique
Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique.
Nouveau!!: Classe de complexité et Informatique théorique · Voir plus »
IP (complexité)
En informatique théorique, et notamment en théorie de la complexité, la classe IP (une abréviation pour, c'est-à-dire « interactif en temps polynomial ») est la classe des problèmes de décision qui peuvent être résolus par un système de preuve interactive.
Nouveau!!: Classe de complexité et IP (complexité) · Voir plus »
L (complexité)
En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée,.
Nouveau!!: Classe de complexité et L (complexité) · Voir plus »
Leonid Levin
Leonid Anatolievich Levin (Леонид Анатольевич Левин, né le à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain.
Nouveau!!: Classe de complexité et Leonid Levin · Voir plus »
Machine de Turing
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.
Nouveau!!: Classe de complexité et Machine de Turing · Voir plus »
Machine de Turing probabiliste
En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard.
Nouveau!!: Classe de complexité et Machine de Turing probabiliste · Voir plus »
Majorant ou minorant
En mathématiques, soient (E, ≤) un ensemble ordonné et F une partie de E; un élément x de E est.
Nouveau!!: Classe de complexité et Majorant ou minorant · Voir plus »
NC (complexité)
En théorie de la complexité, un domaine de l'informatique théorique, NC (pour) est une classe de complexité faisant intervenir le parallélisme.
Nouveau!!: Classe de complexité et NC (complexité) · Voir plus »
NEXPSPACE
NEXPSPACE est une classe de la théorie de la complexité.
Nouveau!!: Classe de complexité et NEXPSPACE · Voir plus »
NEXPTIME
En théorie de la complexité, NEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision.
Nouveau!!: Classe de complexité et NEXPTIME · Voir plus »
NL (complexité)
En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité.
Nouveau!!: Classe de complexité et NL (complexité) · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: Classe de complexité et NP (complexité) · Voir plus »
NSPACE
En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe.
Nouveau!!: Classe de complexité et NSPACE · Voir plus »
NTIME
En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non déterministe.
Nouveau!!: Classe de complexité et NTIME · Voir plus »
P (complexité)
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques.
Nouveau!!: Classe de complexité et P (complexité) · Voir plus »
P/poly
En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales.
Nouveau!!: Classe de complexité et P/poly · Voir plus »
Parallélisme (informatique)
Blue Gene L cabinet, un des supercalculateurs massivement parallèles les plus rapides des années 2000. En informatique, le parallélisme consiste à mettre en œuvre des architectures d'électronique numérique permettant de traiter des informations de manière simultanée, ainsi que les algorithmes spécialisés pour celles-ci.
Nouveau!!: Classe de complexité et Parallélisme (informatique) · Voir plus »
Préordre
En mathématiques, un préordre est une relation binaire réflexive et transitive.
Nouveau!!: Classe de complexité et Préordre · Voir plus »
Problème algorithmique
Un 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.
Nouveau!!: Classe de complexité et Problème algorithmique · Voir plus »
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».
Nouveau!!: Classe de complexité et Problème de décision · Voir plus »
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Nouveau!!: Classe de complexité et Problème NP-complet · Voir plus »
Problème SAT
consulté le.
Nouveau!!: Classe de complexité et Problème SAT · Voir plus »
PSPACE
En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial.
Nouveau!!: Classe de complexité et PSPACE · Voir plus »
Réduction polynomiale
Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.
Nouveau!!: Classe de complexité et Réduction polynomiale · Voir plus »
Relation (mathématiques)
Une relation entre objets mathématiques d'un certain domaine est une propriété qu'ont, ou non, entre eux certains de ces objets; ainsi la relation d'ordre strict, notée « Voir par exemple, p. 36.
Nouveau!!: Classe de complexité et Relation (mathématiques) · Voir plus »
Relation réflexive
En mathématiques, une relation binaire peut avoir, entre autres propriétés, la réflexivité ou bien l'antiréflexivité (ou irréflexivité).
Nouveau!!: Classe de complexité et Relation réflexive · Voir plus »
Relation transitive
En mathématiques, une relation transitive est une relation binaire pour laquelle une suite d'objets reliés consécutivement aboutit à une relation entre le premier et le dernier.
Nouveau!!: Classe de complexité et Relation transitive · Voir plus »
RP (complexité)
Inclusions de classes de complexité probabilistes.En informatique théorique, plus précisément en théorie de la complexité, la classe RP (Randomized Polynomial time) est la classe de complexité des problèmes de décision pour lesquels il existe une machine de Turing probabiliste, en temps polynomial, qui refuse toutes les instances négatives et accepte les instances positives avec une probabilité supérieure à 1/2.
Nouveau!!: Classe de complexité et RP (complexité) · Voir plus »
Stephen Cook
Stephen Arthur Cook (né en 1939 à Buffalo dans l'État de New York) est un informaticien et mathématicien américano-canadien, qui a apporté plusieurs contributions majeures à la théorie de la complexité.
Nouveau!!: Classe de complexité et Stephen Cook · Voir plus »
Système de preuve interactive
Un système de preuve interactive est composé de deux machines abstraites: un prouveur et un vérificateur qui s'échangent des messages. En théorie de la complexité des algorithmes, un système de preuve interactive est un protocole formel de démonstration de théorèmes qui fait intervenir deux participants qui échangent des messages.
Nouveau!!: Classe de complexité et Système de preuve interactive · Voir plus »
Thèse de Cobham
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 foisD. Pisinger, 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, see http://www.diku.dk/forskning/Publikationer/tekniske_rapporter/2003/03-08.pdf, accessed 31 January 2015.). 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.
Nouveau!!: Classe de complexité et Thèse de Cobham · Voir plus »
Théorème de Cook
En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet.
Nouveau!!: Classe de complexité et Théorème de Cook · Voir plus »
Théorème de hiérarchie en temps déterministe
Le théorème de hiérarchie en temps déterministe est un énoncé de la théorie de la complexité, un domaine de l'informatique théorique.
Nouveau!!: Classe de complexité et Théorème de hiérarchie en temps déterministe · Voir plus »
Théorème de Savitch
Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique.
Nouveau!!: Classe de complexité et Théorème de Savitch · Voir plus »
Théorie de la complexité (informatique théorique)
P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.
Nouveau!!: Classe de complexité et Théorie de la complexité (informatique théorique) · Voir plus »
Université de Waterloo
L’Université de Waterloo (UW ou simplement Waterloo) est une université publique de recherche canadienne située à Waterloo, en Ontario.
Nouveau!!: Classe de complexité et Université de Waterloo · Voir plus »
ZPP (complexité)
ZPP et la relation avec d'autres classes de complexité probabilistes. La classe ZPP, est un objet de la théorie de la complexité, en informatique théorique.
Nouveau!!: Classe de complexité et ZPP (complexité) · Voir plus »
