RP (complexité) et Théorie de la complexité (informatique théorique)

Raccourcis: Différences, Similitudes, Jaccard similarité Coefficient, Références.

Différence entre RP (complexité) et Théorie de la complexité (informatique théorique)

RP (complexité) vs. Théorie de la complexité (informatique théorique)

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

Similitudes entre RP (complexité) et Théorie de la complexité (informatique théorique)

RP (complexité) et Théorie de la complexité (informatique théorique) ont 8 choses en commun (em Unionpédia): Classe de complexité, Informatique théorique, Langage formel, Machine de Turing probabiliste, NP (complexité), P (complexité), Problème de décision, Test de primalité AKS.

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.

Classe de complexité et RP (complexité) · Classe de complexité et Théorie de la complexité (informatique théorique) · 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.

Informatique théorique et RP (complexité) · Informatique théorique et Théorie de la complexité (informatique théorique) · Voir plus »

Langage formel

Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots.

Langage formel et RP (complexité) · Langage formel et Théorie de la complexité (informatique théorique) · 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.

Machine de Turing probabiliste et RP (complexité) · Machine de Turing probabiliste et Théorie de la complexité (informatique théorique) · Voir plus »

NP (complexité)

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

NP (complexité) et RP (complexité) · NP (complexité) et Théorie de la complexité (informatique théorique) · 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.

P (complexité) et RP (complexité) · P (complexité) et Théorie de la complexité (informatique théorique) · 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 ».

Problème de décision et RP (complexité) · Problème de décision et Théorie de la complexité (informatique théorique) · Voir plus »

Test de primalité AKS

Le test de primalité AKS (aussi connu comme le test de primalité Agrawal-Kayal-Saxena et le test cyclotomique AKS) est un algorithme de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena (A.K.S).

RP (complexité) et Test de primalité AKS · Test de primalité AKS et Théorie de la complexité (informatique théorique) · Voir plus »

La liste ci-dessus répond aux questions suivantes

Dans ce qui semble RP (complexité) et Théorie de la complexité (informatique théorique)
Quel a en commun RP (complexité) et Théorie de la complexité (informatique théorique)
Similitudes entre RP (complexité) et Théorie de la complexité (informatique théorique)

Comparaison entre RP (complexité) et Théorie de la complexité (informatique théorique)

RP (complexité) a 18 relations, tout en Théorie de la complexité (informatique théorique) a 72. Comme ils ont en commun 8, l'indice de Jaccard est 8.89% = 8 / (18 + 72).

Références

Cet article montre la relation entre RP (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:

Unionpédia est une carte conceptuelle ou réseau sémantique organisée comme une encyclopédie ou un dictionnaire. Il donne une brève définition de chaque concept et de ses relations.

Ceci est une carte mentale en ligne géant qui sert de base pour les schémas conceptuels. Il est libre d'utiliser et de chaque article ou document peut être téléchargé. Il est un outil, ressources ou de référence pour l'étude, la recherche, l'éducation, l'apprentissage ou de l'enseignement, qui peut être utilisé par les enseignants, les éducateurs, les élèves ou étudiants; pour le monde universitaire: à l'école, primaire, secondaire, l'école secondaire, au milieu, un collège, diplôme technique, collégial, universitaire, baccalauréat, de maîtrise ou de doctorat; pour les papiers, des rapports, des projets, des idées, de la documentation, des enquêtes, des résumés, ou une thèse. Voici la définition, l'explication, la description ou la signification de chaque importantes sur lesquelles vous avez besoin d'informations, et une liste de leurs concepts connexes comme un glossaire. Disponible en français, anglais, espagnol, portugais, japonais, chinois, allemand, italien, polonais, néerlandais, russe, arabe, hindi, suédois, ukrainien, hongrois, catalan, tchèque, hébreu, danois, finlandais, indonésien, norvégien, roumain, turc, vietnamien, coréen, thaïlandais, grec, bulgare, croate, slovaque, lituanien, philippin, letton, estonien et slovène. Plus de langues bientôt.

Toutes les informations a été extrait de Wikipédia, et il est disponible sous licence Creative Commons paternité partage à l’identique.

Unionpédia n'est ni approuvée ni affiliée à la Wikimedia Foundation.

Google Play, Android et le logo Google Play sont des marques de Google Inc.

Politique de confidentialité