Accès plus rapide que le navigateur!
25 relations: AC0, Bisimulation, Calcul des prédicats, Classe de complexité, Coloration de graphe, ELEMENTARY (complexité), EXPTIME, Hiérarchie polynomiale, Informatique théorique, Logique d'ordre supérieur, Logique mathématique, Machine de Turing, Mu-calcul, Neil Immerman, NL (complexité), NP (complexité), P (complexité), Problème de décision, PSPACE, Récursivement énumérable, Ronald Fagin, Serge Abiteboul, Théorème de Fagin, Théorie de la complexité (informatique théorique), Théorie des modèles.
AC0
Calculer le ième bit de la somme de deux nombres a et b est dans AC0. L'image montre un circuit de taille polynomiale en la taille de l'entrée, ie. 2n et de profondeur constante (ici de profondeur 5 pour tout n). En théorie de la complexité, AC0 est une classe de complexité définie par des circuits booléens de profondeur constante.
Nouveau!!: Complexité descriptive et AC0 · Voir plus »
Bisimulation
En informatique théorique, une bisimulation est une relation binaire entre systèmes de transition d'états, associant les systèmes qui se comportent de la même façon au sens qu'un des systèmes simule l'autre et vice-versa.
Nouveau!!: Complexité descriptive et Bisimulation · Voir plus »
Calcul des prédicats
En logique mathématique, le calcul des prédicats du premier ordre, logique du premier ordre, calcul des relations, logique quantificationnelle, ou tout simplement calcul des prédicats, est un système formel utilisé pour raisonner et décrire des énoncés en mathématiques, informatique, intelligence artificielle, philosophie et linguistique.
Nouveau!!: Complexité descriptive et Calcul des prédicats · Voir plus »
Classe de complexité
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource.
Nouveau!!: Complexité descriptive et Classe de complexité · Voir plus »
Coloration de graphe
Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente.
Nouveau!!: Complexité descriptive et Coloration de graphe · Voir plus »
ELEMENTARY (complexité)
En théorie de la complexité, la classe de complexité ELEMENTARY des fonctions récursives élémentaires est la réunion des classes de la hiérarchie exponentielle.
Nouveau!!: Complexité descriptive et ELEMENTARY (complexité) · 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!!: Complexité descriptive et EXPTIME · Voir plus »
Hiérarchie polynomiale
En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP.
Nouveau!!: Complexité descriptive et Hiérarchie polynomiale · 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!!: Complexité descriptive et Informatique théorique · Voir plus »
Logique d'ordre supérieur
Les logiques d'ordre supérieur (en anglais, higher-order logic ou HOL) sont des logiques formelles permettant d'utiliser des variables qui réfèrent à des fonctions ou à des prédicats.
Nouveau!!: Complexité descriptive et Logique d'ordre supérieur · Voir plus »
Logique mathématique
La logique mathématique ou métamathématique est une discipline des mathématiques introduite à la fin du, qui s'est donné comme objet l'étude des mathématiques en tant que langage.
Nouveau!!: Complexité descriptive et Logique mathématique · 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!!: Complexité descriptive et Machine de Turing · Voir plus »
Mu-calcul
En logique mathématique et en informatique théorique, le mu-calcul (ou logique du mu-calcul modal) est l'extension de la logique modale classique avec des opérateurs de points fixes.
Nouveau!!: Complexité descriptive et Mu-calcul · Voir plus »
Neil Immerman
Neil Immerman, né le à Manhasset dans l'État de New York, est un informaticien américain, spécialiste de l'informatique théorique, professeur d'informatique à l'université du Massachusetts à Amherst, Computer Science Department, University of Massachusetts Amherst, consulté le 23 janvier 2010.
Nouveau!!: Complexité descriptive et Neil Immerman · 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!!: Complexité descriptive et NL (complexité) · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: Complexité descriptive et NP (complexité) · 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!!: Complexité descriptive et P (complexité) · 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!!: Complexité descriptive et Problème de décision · 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!!: Complexité descriptive et PSPACE · Voir plus »
Récursivement énumérable
En théorie de la calculabilité, un ensemble d'entiers naturels est récursivement énumérable ou semi-décidable si.
Nouveau!!: Complexité descriptive et Récursivement énumérable · Voir plus »
Ronald Fagin
Ronald Fagin (né en 1945) est un informaticien américain, Fellow IBM au IBM Almaden Research Center.
Nouveau!!: Complexité descriptive et Ronald Fagin · Voir plus »
Serge Abiteboul
École normale supérieure de ParisAcadémie des sciencesINRIAAcademia Europaea Serge Abiteboul, né le à Paris, est un informaticien français, membre du Collège de l'ARCEP, chercheur à l'ENS Paris et directeur de recherche à l'Inria.
Nouveau!!: Complexité descriptive et Serge Abiteboul · Voir plus »
Théorème de Fagin
Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles.
Nouveau!!: Complexité descriptive et Théorème de Fagin · 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!!: Complexité descriptive et Théorie de la complexité (informatique théorique) · Voir plus »
Théorie des modèles
La théorie des modèles est une branche de la logique mathématique qui traite de la construction et de la classification des structures.
Nouveau!!: Complexité descriptive et Théorie des modèles · Voir plus »
