Accès plus rapide que le navigateur!
94 relations: Adi Shamir, Alan Turing, Algorithme de Grover, Algorithme de Shor, Algorithme probabiliste, Alonzo Church, Attaque par force brute, Authentification, Axiome, BQP, Cambridge University Press, Christos Papadimitriou, Communications of the ACM, Conjecture, Conjecture de Goldbach, Crible algébrique, Cryptologie, David Hilbert, Décidabilité, Décomposition en produit de facteurs premiers, Disjonction logique, Dollar américain, Elementary (série télévisée), Fonction exponentielle, Formule BBP, Francisco Dória, Générateur de nombres pseudo-aléatoires, Gerhard Woeginger, Gouvernement fédéral des États-Unis, Hypothèse de Riemann, Hypothèse du continu, Informatique, Informatique théorique, Ingénierie, Institut de mathématiques Clay, Interstices, IP (complexité), Jean-Paul Delahaye, Journal of Combinatorial Theory, Journal of Computer and System Sciences, Journal of the ACM, Kurt Gödel, Langage formel, Leonid Levin, Liste de problèmes NP-complets, Logarithme, Machine de Turing, Mathématiques, Michael Sipser, NP (complexité), ..., NP-intermédiaire, Oracle (machine de Turing), Ordinateur quantique, P (complexité), Polynôme, Pour la science, Preuve à divulgation nulle de connaissance, Preuve naturelle, Problème de décision, Problème de l'arrêt, Problème de l'isomorphisme de graphes, Problème de la décision, Problème du voyageur de commerce, Problème NP-complet, Problème SAT, Problèmes de Smale, Problèmes du prix du millénaire, PSPACE, Rajeev Motwani, Relation binaire, Richard E. Ladner, Robin Cousin, Saison 2 d'Elementary, Scott Aaronson, Stephen Cook, Structure algébrique, Symposium on Theory of Computing, Système formel, Test de primalité, Théorème de Cook, Théorème de Goodstein, Théorème de Robertson-Seymour, Théorèmes d'incomplétude de Gödel, Théorie algorithmique de l'information, Théorie de la démonstration, Théorie des ensembles de Zermelo-Fraenkel, Wired (magazine), 1928, 1931, 1936, 1963, 1979, 1993, 21 problèmes NP-complets de Karp. Développer l'indice (44 plus) »
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!!: Problème P ≟ NP et Adi Shamir · Voir plus »
Alan Turing
Alan Turing vers 1938. Alan Mathison Turing, né le à Londres et mort le à Wilmslow, est un mathématicien et cryptologue britannique, auteur de travaux qui fondent scientifiquement l'informatique.
Nouveau!!: Problème P ≟ NP et Alan Turing · Voir plus »
Algorithme de Grover
En informatique quantique, l’algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi N éléments non classés en temps proportionnel à \sqrt et avec un espace de stockage proportionnel à \log(N).
Nouveau!!: Problème P ≟ NP et Algorithme de Grover · Voir plus »
Algorithme de Shor
En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O((\log N)^3) et en espace O(\log N).
Nouveau!!: Problème P ≟ NP et Algorithme de Shor · Voir plus »
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard.
Nouveau!!: Problème P ≟ NP et Algorithme probabiliste · Voir plus »
Alonzo Church
Alonzo Church (Washington - Hudson) est un mathématicien (logicien) américain à qui l'on doit certains des fondements de l'informatique théorique.
Nouveau!!: Problème P ≟ NP et Alonzo Church · Voir plus »
Attaque par force brute
L'attaque par force brute est une méthode utilisée en cryptanalyse pour trouver un mot de passe ou une clé.
Nouveau!!: Problème P ≟ NP et Attaque par force brute · Voir plus »
Authentification
Authentification renforcée basée sur une cryptocard L'authentification est un processus permettant à un système informatique de s'assurer de la légitimité de la demande d'accès faite par une entité (être humain ou un autre système) afin d'autoriser son accès à des ressources du système (système d'exploitation, réseaux, applications…) conformément au paramétrage du contrôle d'accès.
Nouveau!!: Problème P ≟ NP et Authentification · Voir plus »
Axiome
Un axiome (en grec ancien, « principe servant de base à une démonstration, principe évident en soi » – lui-même dérivé de, « juger convenable, croire juste ») est une proposition non démontrée, utilisée comme fondement d’un raisonnement ou d’une théorie mathématique.
Nouveau!!: Problème P ≟ NP et Axiome · Voir plus »
BQP
En théorie de la complexité des algorithmes BQP (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 probabilité d'erreur d'au plus 1/3 dans tous les cas.
Nouveau!!: Problème P ≟ NP et BQP · Voir plus »
Cambridge University Press
Cambridge University Press ou CUP (en français, Presses universitaires de Cambridge) est une maison d'édition universitaire britannique rattachée à l’université de Cambridge.
Nouveau!!: Problème P ≟ NP et Cambridge University Press · Voir plus »
Christos Papadimitriou
Christos Harilaos Papadimitriou (en Χρήστος Χαρίλαος Παπαδημητρίου), né le à Athènes, est un professeur et chercheur en informatique grec.
Nouveau!!: Problème P ≟ NP et Christos Papadimitriou · Voir plus »
Communications of the ACM
Communications of the ACM (CACM) est la principale revue mensuelle de l'Association for Computing Machinery (ACM).
Nouveau!!: Problème P ≟ NP et Communications of the ACM · Voir plus »
Conjecture
En mathématiques, une conjecture est une assertion pour laquelle on ne connaît pas encore de démonstration, mais que l'on croit fortement être vraie (en l'absence de contre-exemple, ou comme généralisation de résultats démontrés).
Nouveau!!: Problème P ≟ NP et Conjecture · Voir plus »
Conjecture de Goldbach
La conjecture de Goldbach est l'assertion mathématique qui s’énonce comme suit: Formulée en 1742 par Christian Goldbach, c’est l’un des plus vieux problèmes non résolus de la théorie des nombres et des mathématiques.
Nouveau!!: Problème P ≟ NP et Conjecture de Goldbach · Voir plus »
Crible algébrique
En théorie des nombres, l'algorithme du crible du corps de nombres généraliséAussi connu sous son nom anglais, generalised number field sieve, ou son acronyme: GNFS.
Nouveau!!: Problème P ≟ NP et Crible algébrique · Voir plus »
Cryptologie
Au cours de la Seconde Guerre mondiale, la machine de Lorenz est exploitée pour chiffrer les communications militaires allemandes de haute importance stratégique ou tactique. La cryptologie, étymologiquement la « science du secret », n'est considérée comme une science que depuis le.
Nouveau!!: Problème P ≟ NP et Cryptologie · Voir plus »
David Hilbert
David Hilbert, né en 1862 à Königsberg et mort en 1943 à Göttingen, est un mathématicien allemand.
Nouveau!!: Problème P ≟ NP et David Hilbert · Voir plus »
Décidabilité
En logique mathématique, le terme décidabilité recouvre deux concepts liés: la décidabilité logique et la décidabilité ''algorithmique''.
Nouveau!!: Problème P ≟ NP et Décidabilité · Voir plus »
Décomposition en produit de facteurs premiers
Décomposition du nombre 864 en facteurs premiers En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers.
Nouveau!!: Problème P ≟ NP et Décomposition en produit de facteurs premiers · Voir plus »
Disjonction logique
La disjonction logique, ou disjonction non exclusive, de deux assertions est une façon d'affirmer qu'au moins une de ces deux assertions est vraie (la première, la deuxième, ou les deux).
Nouveau!!: Problème P ≟ NP et Disjonction logique · Voir plus »
Dollar américain
Le dollar américain ou dollar des États-Unis ou dollar US (symbole monétaire: $; code ISO: USD pour United States dollar) est la monnaie nationale des États-Unis et de ses territoires d'outre-mer (comme Porto Rico); c'est aussi celle de l'Équateur, du Zimbabwe, des États fédérés de Micronésie, des Îles Marshall, des Palaos, du Panama, du Salvador, du Timor oriental, des Îles Turques-et-Caïques, des Îles Vierges britanniques et des Îles BES.
Nouveau!!: Problème P ≟ NP et Dollar américain · Voir plus »
Elementary (série télévisée)
ou Élémentaire au Québec est une série télévisée américaine en 154 épisodes de 42 minutes créée par Robert Doherty et diffusée entre le et le sur le réseau CBS aux États-Unis et en simultané sur le réseau Global au Canada.
Nouveau!!: Problème P ≟ NP et Elementary (série télévisée) · Voir plus »
Fonction exponentielle
En mathématiques, la fonction exponentielle est la fonction notée qui est égale à sa propre dérivée et prend la valeur en.
Nouveau!!: Problème P ≟ NP et Fonction exponentielle · Voir plus »
Formule BBP
La formule BBP (ou formule de Bailey-Borwein-Plouffe) permet de calculer le n-ième chiffre après la virgule du π en base 2 (ou 16) sans avoir à en calculer les précédents, et en utilisant très peu de mémoire et de temps.
Nouveau!!: Problème P ≟ NP et Formule BBP · Voir plus »
Francisco Dória
Francisco Antônio de Moraes Accioli Dória (né le à Rio de Janeiro, Brésil) est un mathématicien, philosophe et généalogiste brésilien.
Nouveau!!: Problème P ≟ NP et Francisco Dória · Voir plus »
Générateur de nombres pseudo-aléatoires
Un générateur de nombres pseudo-aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard.
Nouveau!!: Problème P ≟ NP et Générateur de nombres pseudo-aléatoires · Voir plus »
Gerhard Woeginger
Gerhard J. Woeginger, né le à Graz, en Autriche et mort le, est un mathématicien et informaticien autrichien.
Nouveau!!: Problème P ≟ NP et Gerhard Woeginger · Voir plus »
Gouvernement fédéral des États-Unis
Le Gouvernement fédéral des États-Unis est le Gouvernement national des États-Unis, une République fédérale d'Amérique du Nord composée de, d'un district (Washington, D.C.) et de plusieurs territoires.
Nouveau!!: Problème P ≟ NP et Gouvernement fédéral des États-Unis · Voir plus »
Hypothèse de Riemann
En mathématiques, l'hypothèse de Riemann est une conjecture formulée en 1859 par le mathématicien allemand Bernhard Riemann, selon laquelle les zéros non triviaux de la fonction zêta de Riemann ont tous une partie réelle égale à 1/2.
Nouveau!!: Problème P ≟ NP et Hypothèse de Riemann · Voir plus »
Hypothèse du continu
En théorie des ensembles, l'hypothèse du continu (HC), due à Georg Cantor, affirme qu'il n'existe aucun ensemble dont le cardinal est strictement compris entre le cardinal de l'ensemble des entiers naturels et celui de l'ensemble des nombres réels.
Nouveau!!: Problème P ≟ NP et Hypothèse du continu · Voir plus »
Informatique
bibliothèque d'Art et d'Archéologie de Genève (2017). L'informatique est un domaine d'activité scientifique, technique, et industriel concernant le traitement automatique de l'information numérique par l'exécution de programmes informatiques hébergés par des dispositifs électriques-électroniques: des systèmes embarqués, des ordinateurs, des robots, des automates Ces champs d'application peuvent être séparés en deux branches.
Nouveau!!: Problème P ≟ NP et Informatique · 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!!: Problème P ≟ NP et Informatique théorique · Voir plus »
Ingénierie
L'ingénierie est l'ensemble des fonctions qui mènent de la conception et des études, de l'achat et du contrôle de fabrication des équipements, à la construction et à la mise en service d'une installation technique ou industrielle.
Nouveau!!: Problème P ≟ NP et Ingénierie · Voir plus »
Institut de mathématiques Clay
L’institut de mathématiques Clay (en anglais, Clay Mathematics Institute, ou CMI) a été fondé en par Landon Clay, un homme d'affaires de Boston, président-directeur général de « East Hill Management », et son épouse Lavinia Clay dans le but de promouvoir et disséminer la connaissance mathématique dans le monde, en instaurant un système de prix pour les chercheurs mathématiciens.
Nouveau!!: Problème P ≟ NP et Institut de mathématiques Clay · Voir plus »
Interstices
interstices est une revue de culture scientifique en ligne, créée par des chercheurs de l'INRIA pour rendre accessible à un large public la recherche en informatique.
Nouveau!!: Problème P ≟ NP et Interstices · 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!!: Problème P ≟ NP et IP (complexité) · Voir plus »
Jean-Paul Delahaye
Jean-Paul Delahaye est un informaticien et mathématicien français né à Saint-Mandé (Seine) le.
Nouveau!!: Problème P ≟ NP et Jean-Paul Delahaye · Voir plus »
Journal of Combinatorial Theory
Le Journal of Combinatorial Theory, Series A et Series B est une revue mathématique se spécialisant en analyse combinatoire et autres questions associées; elle est publiée par Elsevier Science.
Nouveau!!: Problème P ≟ NP et Journal of Combinatorial Theory · Voir plus »
Journal of Computer and System Sciences
Le Journal of Computer and System Sciences (abrégé en « JCSS ») est une revue scientifique dans le domaine de l'informatique théorique dont les publications sont basées sur le principe de l'évaluation par les pairs.
Nouveau!!: Problème P ≟ NP et Journal of Computer and System Sciences · 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!!: Problème P ≟ NP et Journal of the ACM · Voir plus »
Kurt Gödel
Kurt Gödel, né le à Brünn et mort le à Princeton (New Jersey), est un logicien et mathématicien autrichien naturalisé américain.
Nouveau!!: Problème P ≟ NP et Kurt Gödel · Voir plus »
Langage formel
Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots.
Nouveau!!: Problème P ≟ NP et Langage formel · Voir plus »
Leonid Levin
Leonid Anatolievich Levin (Леонид Анатольевич Левин, né le à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain.
Nouveau!!: Problème P ≟ NP et Leonid Levin · Voir plus »
Liste de problèmes NP-complets
Ceci est une liste des problèmes NP-complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d'un problème de décision.
Nouveau!!: Problème P ≟ NP et Liste de problèmes NP-complets · Voir plus »
Logarithme
e et 10. En mathématiques, un logarithme est la fonction réciproque d'une exponentiation, c'est-à-dire que le logarithme de base d'un nombre réel strictement positif est la puissance à laquelle il faut élever la base pour obtenir ce nombre.
Nouveau!!: Problème P ≟ NP et Logarithme · 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!!: Problème P ≟ NP et Machine de Turing · Voir plus »
Mathématiques
Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets.
Nouveau!!: Problème P ≟ NP et Mathématiques · Voir plus »
Michael Sipser
Michael Fredric Sipser est professeur de mathématiques appliquées et chercheur dans le groupe au MIT.
Nouveau!!: Problème P ≟ NP et Michael Sipser · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: Problème P ≟ NP et NP (complexité) · Voir plus »
NP-intermédiaire
En théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI.
Nouveau!!: Problème P ≟ NP et NP-intermédiaire · Voir plus »
Oracle (machine de Turing)
Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire.
Nouveau!!: Problème P ≟ NP et Oracle (machine de Turing) · Voir plus »
Ordinateur quantique
qubits et la deuxième un qubit, les boîtes représentent des opérations, et le diagramme se lit de gauche à droite correspondant à la chronologie des opérationshttps://blogs.msdn.microsoft.com/visualstudio/2018/12/01/qubits-in-qsharp/. Un ordinateur quantique, calculateur quantique, processeur quantique ou système informatique quantique, utilise les propriétés quantiques de la matière, telles que la superposition et l'intrication, afin d'effectuer des opérations sur des données.
Nouveau!!: Problème P ≟ NP et Ordinateur quantique · 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.
Nouveau!!: Problème P ≟ NP et P (complexité) · 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!!: Problème P ≟ NP et Polynôme · Voir plus »
Pour la science
Pour la science est une revue mensuelle de vulgarisation scientifique française fondée en 1977.
Nouveau!!: Problème P ≟ NP et Pour la science · Voir plus »
Preuve à divulgation nulle de connaissance
Une preuve à divulgation nulle de connaissance est une brique de base utilisée en cryptologie dans le cadre de l'authentification et de l'identification.
Nouveau!!: Problème P ≟ NP et Preuve à divulgation nulle de connaissance · Voir plus »
Preuve naturelle
En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés.
Nouveau!!: Problème P ≟ NP et Preuve naturelle · 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!!: Problème P ≟ NP et Problème de décision · Voir plus »
Problème de l'arrêt
L'animation illustre une machine impossible: il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.
Nouveau!!: Problème P ≟ NP et Problème de l'arrêt · Voir plus »
Problème de l'isomorphisme de graphes
Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets.
Nouveau!!: Problème P ≟ NP et Problème de l'isomorphisme de graphes · Voir plus »
Problème de la décision
En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples: système à la Hilbert, calcul des séquents, déduction naturelle).
Nouveau!!: Problème P ≟ NP et Problème de la décision · Voir plus »
Problème du voyageur de commerce
Le problème de voyageur de commerce: calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois.
Nouveau!!: Problème P ≟ NP et Problème du voyageur de commerce · 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!!: Problème P ≟ NP et Problème NP-complet · Voir plus »
Problème SAT
consulté le.
Nouveau!!: Problème P ≟ NP et Problème SAT · Voir plus »
Problèmes de Smale
En mathématiques, les problèmes de Smale forment une liste de 18 problèmes non résolus en mathématiques, proposée par Steve Smale en 2000.
Nouveau!!: Problème P ≟ NP et Problèmes de Smale · Voir plus »
Problèmes du prix du millénaire
Les problèmes du prix du millénaire sont un ensemble de sept défis mathématiques réputés insurmontables, posés par l'Institut de mathématiques Clay en.
Nouveau!!: Problème P ≟ NP et Problèmes du prix du millénaire · Voir plus »
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.
Nouveau!!: Problème P ≟ NP et PSPACE · Voir plus »
Rajeev Motwani
Rajeev Motwani (राजीव मोटवानी; -) était un professeur et chercheur en informatique théorique à l'Université Stanford.
Nouveau!!: Problème P ≟ NP et Rajeev Motwani · Voir plus »
Relation binaire
En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est définie par un sous-ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la seconde dans F. Cette collection est désignée par le graphe de la relation.
Nouveau!!: Problème P ≟ NP et Relation binaire · 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!!: Problème P ≟ NP et Richard E. Ladner · Voir plus »
Robin Cousin
Robin Cousin, né le dans les Hautes-Pyrénées, est un auteur de bande dessinée français.
Nouveau!!: Problème P ≟ NP et Robin Cousin · Voir plus »
Saison 2 d'Elementary
Cet article présente les vingt-quatre épisodes de la deuxième saison de la série télévisée américaine Elementary.
Nouveau!!: Problème P ≟ NP et Saison 2 d'Elementary · Voir plus »
Scott Aaronson
Scott Joel Aaronson, est un chercheur, professeur et vulgarisateur en informatique théorique, notamment en informatique quantique.
Nouveau!!: Problème P ≟ NP et Scott Aaronson · Voir plus »
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é.
Nouveau!!: Problème P ≟ NP et Stephen Cook · Voir plus »
Structure algébrique
En mathématiques, une structure algébrique est définie axiomatiquement par une ou plusieurs opérations sur un ensemble (dites internes), éventuellement muni d’autres opérations (externes) dépendant d’autres ensembles, toutes ces opérations satisfaisant certaines relations telles que l’associativité, la commutativité ou la distributivité.
Nouveau!!: Problème P ≟ NP et Structure algébrique · Voir plus »
Symposium on Theory of Computing
La conférence Annual ACM Symposium on Theory of Computing (abrégé en STOC) est une conférence scientifique dans le domaine de l’informatique théorique.
Nouveau!!: Problème P ≟ NP et Symposium on Theory of Computing · Voir plus »
Système formel
Un système formel est une modélisation mathématique d'un langage en général spécialisé.
Nouveau!!: Problème P ≟ NP et Système formel · Voir plus »
Test de primalité
date.
Nouveau!!: Problème P ≟ NP et Test de primalité · Voir plus »
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.
Nouveau!!: Problème P ≟ NP et Théorème de Cook · Voir plus »
Théorème de Goodstein
En mathématiques, et plus précisément en logique mathématique, le théorème de Goodstein est un énoncé arithmétique portant sur des suites, dites suites de Goodstein.
Nouveau!!: Problème P ≟ NP et Théorème de Goodstein · Voir plus »
Théorème de Robertson-Seymour
En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre).
Nouveau!!: Problème P ≟ NP et Théorème de Robertson-Seymour · Voir plus »
Théorèmes d'incomplétude de Gödel
Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »).
Nouveau!!: Problème P ≟ NP et Théorèmes d'incomplétude de Gödel · Voir plus »
Théorie algorithmique de l'information
La théorie algorithmique de l'information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d'un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing.
Nouveau!!: Problème P ≟ NP et Théorie algorithmique de l'information · Voir plus »
Théorie de la démonstration
La théorie de la démonstration, aussi connue sous le nom de théorie de la preuve (de l'anglais), est une branche de la logique mathématique.
Nouveau!!: Problème P ≟ NP et Théorie de la démonstration · Voir plus »
Théorie des ensembles de Zermelo-Fraenkel
L'appartenance En mathématiques, la théorie des ensembles de Zermelo-Fraenkel, abrégée en ZF, est une axiomatisation en logique du premier ordre de la théorie des ensembles telle qu'elle avait été développée dans le dernier quart du par Georg Cantor.
Nouveau!!: Problème P ≟ NP et Théorie des ensembles de Zermelo-Fraenkel · Voir plus »
Wired (magazine)
Wired (terme anglophone signifiant branché ou câblé) est un magazine mensuel américain publié sur papier et en ligne.
Nouveau!!: Problème P ≟ NP et Wired (magazine) · Voir plus »
1928
L'année 1928 est une année bissextile qui commence un dimanche.
Nouveau!!: Problème P ≟ NP et 1928 · Voir plus »
1931
L'année 1931 est une année commune qui commence un jeudi.
Nouveau!!: Problème P ≟ NP et 1931 · Voir plus »
1936
L'année 1936 est une année bissextile qui commence un mercredi.
Nouveau!!: Problème P ≟ NP et 1936 · Voir plus »
1963
L'année 1963 est une année commune qui commence un mardi.
Nouveau!!: Problème P ≟ NP et 1963 · Voir plus »
1979
L'année 1979 est une année commune qui commence un lundi.
Nouveau!!: Problème P ≟ NP et 1979 · Voir plus »
1993
L'année 1993 est une année commune qui commence un vendredi.
Nouveau!!: Problème P ≟ NP et 1993 · Voir plus »
21 problèmes NP-complets de Karp
Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes.
Nouveau!!: Problème P ≟ NP et 21 problèmes NP-complets de Karp · Voir plus »
Redirections ici:
P = NP, P=NP, Problème P = NP, Problème P=NP.
