Logo
Unionpédia
Communication
Disponible sur Google Play
Nouveau! Téléchargez Unionpédia sur votre appareil Android™!
Installer
Accès plus rapide que le navigateur!
 

PSPACE

Indice 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.

42 relations: Adi Shamir, Borne supérieure et borne inférieure, Calcul des prédicats, Calcul des propositions, Classe de complexité, Complexité en espace, CTL*, Expression régulière, EXPSPACE, EXPTIME, Formule booléenne quantifiée, Géographie généralisée, Hex, Hiérarchie polynomiale, Informatique théorique, IP (complexité), Journal of the ACM, Logique contrainte, Logique intuitionniste, Logique modale, Logique temporelle, Logique temporelle linéaire, Machine de Turing, Machine de Turing alternante, Massachusetts Institute of Technology, Morpion (jeu), NEXPTIME, NL (complexité), NP (complexité), Othello (jeu), Planification (intelligence artificielle), Polynôme, Problème de décision, Problème de plus court chemin, Problème NP-complet, Richard E. Ladner, STRIPS, Système de preuve interactive, Théorème d'Immerman-Szelepcsényi, Théorème de Savitch, Théorie de la complexité (informatique théorique), Vérification de modèles.

Adi Shamir

Adi Shamir (en hébreu עדי שמיר), né le à Tel Aviv, est un mathématicien et un cryptologue israélien reconnu comme l'un des experts les plus éminents en cryptanalyse.

Nouveau!!: PSPACE et Adi Shamir · Voir plus »

Borne supérieure et borne inférieure

En mathématiques, les notions de borne supérieure et borne inférieure d'un ensemble de nombres réels interviennent en analyse, comme cas particulier de la définition générale suivante: la borne supérieure (ou le supremum) d'une partie d'un ensemble (partiellement) ordonné est le plus petit de ses majorants.

Nouveau!!: PSPACE et Borne supérieure et borne inférieure · 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!!: PSPACE et Calcul des prédicats · Voir plus »

Calcul des propositions

Le calcul des propositions ou calcul propositionnel, (ou encore logique des propositions) fait partie de la logique mathématique.

Nouveau!!: PSPACE et Calcul des propositions · 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!!: PSPACE et Classe de 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!!: PSPACE et Complexité en espace · Voir plus »

CTL*

En informatique théorique, notamment en vérification formelle, CTL* (prononcé en anglais) est une logique temporelle.

Nouveau!!: PSPACE et CTL* · Voir plus »

Expression régulière

Stephen Cole Kleene, dont les travaux ont fondé le concept d'expression régulière. En informatique, une expression régulière ou expression rationnelle ou expression normaleD'après la de la norme ISO/IEC 9075:1989 par le Conseil du Trésor du Canada et qui est par le Bureau de la traduction du gouvernement du Canada.

Nouveau!!: PSPACE et Expression régulière · 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!!: PSPACE 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!!: PSPACE et EXPTIME · Voir plus »

Formule booléenne quantifiée

En théorie de la complexité, en informatique théorique, en logique mathématique, une formule booléenne quantifiée (ou formule QBF pour en anglais) est une formule de la logique propositionnelle où les variables propositionnelles sont quantifiées.

Nouveau!!: PSPACE et Formule booléenne quantifiée · Voir plus »

Géographie généralisée

En théorie de la complexité, géographie généralisé est un problème PSPACE-complet classique.

Nouveau!!: PSPACE et Géographie généralisée · Voir plus »

Hex

Le jeu de Hex est un jeu de société combinatoire abstrait pour deux joueurs.

Nouveau!!: PSPACE et Hex · 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!!: PSPACE 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!!: PSPACE 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!!: PSPACE et IP (complexité) · Voir plus »

Journal of the ACM

Journal of the ACM (Journal de l'ACM) est la revue scientifique majeure de l'Association for Computing Machinery (ACM).

Nouveau!!: PSPACE et Journal of the ACM · Voir plus »

Logique contrainte

En informatique théorique et en théorie des jeux, la logique contrainte (nom original en anglais: constraint logic) est un formalisme proposé par Robert A. Hearn et Erik D. Demaine.

Nouveau!!: PSPACE et Logique contrainte · Voir plus »

Logique intuitionniste

La logique intuitionniste est une logique qui diffère de la logique classique par le fait que la notion de vérité est remplacée par la notion de preuve constructive.

Nouveau!!: PSPACE et Logique intuitionniste · Voir plus »

Logique modale

En logique mathématique, une logique modale est un type de logique formelle qui étend la logique propositionnelle, la logique du premier ordre ou la logique d'ordre supérieur avec des modalités.

Nouveau!!: PSPACE et Logique modale · Voir plus »

Logique temporelle

La logique temporelle est une branche de la logique mathématique et plus précisément de la logique modale, qui est formalisée de plusieurs manières.

Nouveau!!: PSPACE et Logique temporelle · Voir plus »

Logique temporelle linéaire

En logique, la logique temporelle linéaire (LTL) est une logique temporelle modale avec des modalités se référant au temps.

Nouveau!!: PSPACE et Logique temporelle linéaire · 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!!: PSPACE et Machine de Turing · Voir plus »

Machine de Turing alternante

En 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.

Nouveau!!: PSPACE et Machine de Turing alternante · Voir plus »

Massachusetts Institute of Technology

Le grand dôme du MIT. Le Massachusetts Institute of Technology (MIT), en français Institut de technologie du Massachusetts, est un institut de recherche américain et une université, spécialisé dans les domaines de la science et de la technologie.

Nouveau!!: PSPACE et Massachusetts Institute of Technology · Voir plus »

Morpion (jeu)

Exemple d'une partie de morpion Le morpion est un jeu de réflexion se pratiquant à deux joueurs au tour par tour et dont le but est de créer le premier un alignement sur une grille.

Nouveau!!: PSPACE et Morpion (jeu) · 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!!: PSPACE 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!!: PSPACE et NL (complexité) · Voir plus »

NP (complexité)

La classe NP est une classe très importante de la théorie de la complexité.

Nouveau!!: PSPACE et NP (complexité) · Voir plus »

Othello (jeu)

Othello (aussi connu sous le nom Reversi) est un jeu de société combinatoire abstrait opposant deux joueurs.

Nouveau!!: PSPACE et Othello (jeu) · Voir plus »

Planification (intelligence artificielle)

257x257px En intelligence artificielle, la planification automatique (automated planning en anglais) ou plus simplement planification, vise à développer des algorithmes pour produire des plans typiquement pour l'exécution par un robot ou tout autre agent.

Nouveau!!: PSPACE et Planification (intelligence artificielle) · Voir plus »

Polynôme

Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées (aussi appelées variables), habituellement notées X, Y, Z, etc.

Nouveau!!: PSPACE et Polynôme · 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!!: PSPACE et Problème de décision · Voir plus »

Problème de plus court chemin

Exemple d'un plus court chemin du sommet A au sommet F: (A, C, E, D, F). En théorie des graphes, le problème de plus court chemin est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale.

Nouveau!!: PSPACE et Problème de plus court chemin · 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!!: PSPACE et Problème NP-complet · Voir plus »

Richard E. Ladner

Richard Emil Ladner est un informaticien américain connu pour ses contributions à la fois à l'informatique théorique et aux.

Nouveau!!: PSPACE et Richard E. Ladner · Voir plus »

STRIPS

Shakey de SRI International (ici en 1972) utilisait l'algorithme STRIPS. STRIPS (ou Stanford Research Institute problem solver) est un algorithme de planification classique conçu par et Nils John Nilsson en 1971.

Nouveau!!: PSPACE et STRIPS · 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!!: PSPACE et Système de preuve interactive · Voir plus »

Théorème d'Immerman-Szelepcsényi

Le théorème d'Immerman-Szelepcsényi est un théorème d'informatique théorique, et notamment de la théorie de la complexité, démontré en 1987 indépendamment par Neil Immerman et Róbert Szelepcsényi, et qui leur a valu d'obtenir conjointement le prix Gödel en 1995.

Nouveau!!: PSPACE et Théorème d'Immerman-Szelepcsényi · 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!!: PSPACE 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!!: PSPACE et Théorie de la complexité (informatique théorique) · Voir plus »

Vérification de modèles

model checking''. En informatique, la vérification de modèles, ou en anglais, est le problème suivant: vérifier si le modèle d'un système (souvent informatique ou électronique) satisfait une propriété.

Nouveau!!: PSPACE et Vérification de modèles · Voir plus »

Redirections ici:

CoNPSPACE, NPSPACE, P = PSPACE, PSPACE-complet.

SortantEntrants
Hey! Nous sommes sur Facebook maintenant! »