Similitudes entre Classe de complexité et Théorie de la complexité (informatique théorique)
Classe de complexité et Théorie de la complexité (informatique théorique) ont 19 choses en commun (em Unionpédia): Complexité en temps, EXPSPACE, EXPTIME, Informatique théorique, L (complexité), Leonid Levin, Machine de Turing, Machine de Turing probabiliste, NEXPTIME, NL (complexité), NP (complexité), P (complexité), Problème algorithmique, Problème de décision, PSPACE, Réduction polynomiale, Stephen Cook, Théorème de Cook, Théorème de Savitch.
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.
Classe de complexité et Complexité en temps · Complexité en temps et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et EXPSPACE · EXPSPACE et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et EXPTIME · EXPTIME et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et Informatique théorique · Informatique théorique et Théorie de la complexité (informatique théorique) ·
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,.
Classe de complexité et L (complexité) · L (complexité) et Théorie de la complexité (informatique théorique) ·
Leonid Levin
Leonid Anatolievich Levin (Леонид Анатольевич Левин, né le à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain.
Classe de complexité et Leonid Levin · Leonid Levin et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et Machine de Turing · Machine de Turing et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et Machine de Turing probabiliste · Machine de Turing probabiliste et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et NEXPTIME · NEXPTIME et Théorie de la complexité (informatique théorique) ·
NL (complexité)
En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité.
Classe de complexité et NL (complexité) · NL (complexité) et Théorie de la complexité (informatique théorique) ·
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Classe de complexité et NP (complexité) · NP (complexité) et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et P (complexité) · P (complexité) et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et Problème algorithmique · Problème algorithmique et Théorie de la complexité (informatique théorique) ·
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 ».
Classe de complexité et Problème de décision · Problème de décision et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et PSPACE · PSPACE et Théorie de la complexité (informatique théorique) ·
Réduction polynomiale
Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.
Classe de complexité et Réduction polynomiale · Réduction polynomiale et Théorie de la complexité (informatique théorique) ·
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é.
Classe de complexité et Stephen Cook · Stephen Cook et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et Théorème de Cook · Théorème de Cook et Théorie de la complexité (informatique théorique) ·
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.
Classe de complexité et Théorème de Savitch · Théorème de Savitch et Théorie de la complexité (informatique théorique) ·
La liste ci-dessus répond aux questions suivantes
- Dans ce qui semble Classe de complexité et Théorie de la complexité (informatique théorique)
- Quel a en commun Classe de complexité et Théorie de la complexité (informatique théorique)
- Similitudes entre Classe de complexité et Théorie de la complexité (informatique théorique)
Comparaison entre Classe de complexité et Théorie de la complexité (informatique théorique)
Classe de complexité a 50 relations, tout en Théorie de la complexité (informatique théorique) a 72. Comme ils ont en commun 19, l'indice de Jaccard est 15.57% = 19 / (50 + 72).
Références
Cet article montre la relation entre Classe de complexité et Théorie de la complexité (informatique théorique). Pour accéder à chaque article à partir de laquelle l'information a été extraite, s'il vous plaît visitez: