Bibliothèque Tangente. N° 55. Réduire la taille d’une preuve. p. 152-155.
Auteur : Schabanel Nicolas
Résumé
Il est possible de réduire la longueur d’une preuve d’une taille exponentielle, comme nous l’apprend le petit théorème PCP, à une taille polynomiale. Pour cela, des graphes quelque peu particuliers vont se révéler très utiles. Cet article présente quelques grandes lignes de la preuve de PCP version optimisée.
Notes
Cet article est publié sous la rubrique « Savoirs ».
Il fait partie du dossier : Les apports de l’informatique dans Bibliothèque Tangente n° 55 – Les démonstrations.
Données de publication
Éditeur Editions POLE Paris , 2015 Collection Bibliothèque Tangente Num. 55 Format 17 cm x 24 cm, p. 148-151
ISBN 2-84884-198-2 EAN 9782848841984 ISSN 2263-4908
Public visé élève ou étudiant, enseignant, tout public Niveau 1re, 2de, licence, lycée, terminale Âge 15, 16, 17, 18, 19
Type chapitre d’un ouvrage, vulgarisation, popularisation Langue français Support papier
Classification