Similitudes entre NC (complexité) et P (complexité)
NC (complexité) et P (complexité) ont 8 choses en commun (em Unionpédia): Circuit booléen, Hiérarchie polynomiale, Informatique théorique, L (complexité), NL (complexité), Problème de décision, Problème de l'évaluation d'un circuit, Théorie de la complexité (informatique théorique).
Circuit booléen
Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles.
Circuit booléen et NC (complexité) · Circuit booléen et P (complexité) ·
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.
Hiérarchie polynomiale et NC (complexité) · Hiérarchie polynomiale et P (complexité) ·
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.
Informatique théorique et NC (complexité) · Informatique théorique et P (complexité) ·
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,.
L (complexité) et NC (complexité) · L (complexité) et P (complexité) ·
NL (complexité)
En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité.
NC (complexité) et NL (complexité) · NL (complexité) et P (complexité) ·
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 ».
NC (complexité) et Problème de décision · P (complexité) et Problème de décision ·
Problème de l'évaluation d'un circuit
Exemple d'un circuit avec deux entrées 1 et 0. La sortie vaut 1 (cliquer sur l'image pour voir l'animation qui calcule la sortie). En informatique théorique, plus précisément en théorie de la complexité, le problème de l'évaluation d'un circuit (appelé CIRCUIT VALUE PROBLEM, CVP, CIRCUIT EVALUATION PROBLEM ou CIRCUIT-EVAL en anglais) est le problème de décision qui consiste à calculer la sortie d'un circuit booléen sur des entrées données.
NC (complexité) et Problème de l'évaluation d'un circuit · P (complexité) et Problème de l'évaluation d'un circuit ·
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.
NC (complexité) et Théorie de la complexité (informatique théorique) · P (complexité) et Théorie de la complexité (informatique théorique) ·
La liste ci-dessus répond aux questions suivantes
- Dans ce qui semble NC (complexité) et P (complexité)
- Quel a en commun NC (complexité) et P (complexité)
- Similitudes entre NC (complexité) et P (complexité)
Comparaison entre NC (complexité) et P (complexité)
NC (complexité) a 19 relations, tout en P (complexité) a 42. Comme ils ont en commun 8, l'indice de Jaccard est 13.11% = 8 / (19 + 42).
Références
Cet article montre la relation entre NC (complexité) et P (complexité). Pour accéder à chaque article à partir de laquelle l'information a été extraite, s'il vous plaît visitez: