Collection · Mathématiques
Théorie de la complexité
Dans Sciences
52 cartes9 joueurs l'ont commencée
Collection « Théorie de la complexité » sur Wikicard : 52 cartes tirées de Wikipédia, dont P (complexité), NP (complexité), Problème NP-complet. Terminée, elle donne un badge brodé « Argent », généré pour elle par IA.
Ses cartes
Théorie de la complexité (informatique théorique)LégendaireLa 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…
Problème NP-completÉpiqueUn 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 : il est possible de…
- NP (complexité)ÉpiqueNP est une classe très importante de la théorie de la complexité.
- P (complexité)ÉpiquePTIME 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éRareUne classe de complexité est un ensemble de problèmes de décision dont la résolution nécessite la même quantité d'une certaine ressource.
- Réduction polynomialeRareUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.
- PSPACERarePSPACE 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.
- Théorème de CookRareThé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.
- PP (complexité)RarePP est un objet de la théorie de la complexité, un domaine de l'informatique théorique.
- NC (complexité)RareNC (pour Nick's class) est une classe de complexité faisant intervenir le parallélisme.
- NL (complexité)RareNL est une classe de complexité.
- Co-NPRareCo-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision au sens de la théorie de la complexité.
Sharp-PRare#P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problème de décision qui est dans la classe NP.- BPP (complexité)RareBPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité…
- EXPTIMERareEXPTIME (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.
BQPRareBQP (bounded error quantum polynomial time) est la classe des problèmes de décision qui peuvent être résolus par un calculateur quantique en un temps polynomial, avec une…
- 21 problèmes NP-complets de KarpRareLes 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes.
Hiérarchie polynomialeRareLa hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP.
- L (complexité)RareLe est une ébauche concernant l’informatique théorique.
RP (complexité)RareRP (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…
- Théorème PCPPeu communeLe théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la…
- Théorème de SavitchPeu communeLe théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique.
- EXPSPACEPeu communeEXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe.
ZPP (complexité)Peu communeZPP, est un objet de la théorie de la complexité, en informatique théorique.
AC0Peu communeAC0 est une classe de complexité définie par des circuits booléens de profondeur constante.
- NEXPTIMEPeu communeNEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision.
- P/polyPeu communeP/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales.
- APX (complexité)Peu communeAPX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant.
- IP (complexité)Peu communeIP (une abréviation pour Interactive Polynomial time, c'est-à-dire « interactif en temps polynomial ») est la classe des problèmes de décision qui peuvent être résolus par un…
- DTIMEPeu communeDTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe.
- DSPACEPeu communeDSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing déterministe.
- Sharp-P-completPeu commune#P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique.
- Liste de classes de complexitéPeu communeCet article présente une liste de classes de complexité en théorie de la complexité.
- E (complexité)Peu communeE est une classe de complexité ; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing déterministe en temps exponentiel avec un exposant…
- KernelisationPeu communeLa kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier.
- NSPACEPeu communeNSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe.
- Théorème d'accélération linéairePeu communeLe théorème d'accélération linéaire ou de speedup linéaire est un théorème de théorie de la complexité, un domaine de l'informatique théorique.
- PH (complexité)Peu communePH est l'union des classes de complexité de la hiérarchie polynomiale : P H = ⋃ k ∈ N Σ k P {\displaystyle {\mathsf {PH}}=\bigcup _{k\in \mathbb {N} }\Sigma _{k}^{\mathsf {P}}} PH…
- Protocole Arthur-MerlinPeu communeUn protocole Arthur-Merlin est un système de preuve interactive dans lequel on impose que les lancers de pièces du vérificateur soient publics (c'est-à-dire également connus du…
- Théorème de TodaPeu communeLe théorème de Toda est un résultat en théorie de la complexité, démontré en 1991 par Seinosuke Toda dans son article PP is as Hard as the Polynomial-Time Hierarchy, et qui a valu…
- Théorème d'Immerman-SzelepcsényiPeu communeLe 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…
- NTIMEPeu communeNTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non déterministe.
- UP (complexité)Peu communeUP (en anglais : unambigous non-deterministic polynomial time) est la classe de complexité des problèmes de décision décidés par une machine de Turing non ambigüe (machine de…
- NP-facilePeu communeNP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP.
- Théorème de Sipser-Gács-LautemannPeu communeLe théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est le théorème qui énonce que la classe probabiliste BPP (bounded-error probabilistic…
- Théorème de Karp-LiptonCommuneEn théorie de la complexité, le théorème de Karp–Lipton affirme que si le problème de satisfiabilité booléenne (SAT) est résolu par une famille de circuits booléens avec un nombre…
- NE (complexité)Peu communeNE est une classe de complexité ; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing non déterministe en temps exponentiel avec un…
- Complexité impliciteCommuneLa complexité implicite est une branche de la théorie de la complexité calculatoire qui caractérise les classes de complexité par des restrictions syntaxiques sur le langage de…
- Fonction constructibleCommuneUne fonction constructible en temps est une fonction f des entiers naturels vers les entiers naturels, avec la propriété que f(n) peut être calculée à partir de n par une machine…
- AC (complexité)CommuneAC est la classe de complexité définie comme l'union des ACi, où ACi est la classe de complexité des problèmes décidés par des circuits booléens de profondeur O ( log i n )…
- NEXPSPACECommuneNEXPSPACE est une classe de la théorie de la complexité.
- Conseil (informatique théorique)CommuneUn conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage.
Ouvrez des paquets de cartes tirées de Wikipédia, terminez vos collections pour gagner leur badge brodé, défiez d'autres joueurs en Joute. Gratuit, sans avantage payant.